summaryrefslogtreecommitdiff
path: root/src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc
diff options
context:
space:
mode:
Diffstat (limited to 'src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc')
-rw-r--r--src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc76
1 files changed, 0 insertions, 76 deletions
diff --git a/src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc b/src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc
deleted file mode 100644
index 2b4a8a2..0000000
--- a/src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc
+++ /dev/null
@@ -1,76 +0,0 @@
-= SICP persistent amortized O(1) queue
-
-[source,scheme]
-----
-(define (queue)
- (cons '()
- '()))
-
-(define (enqueue x q)
- (cons (car q)
- (cons x (cdr q))))
-
-(define (flush q)
- (cons (reverse (cdr q))
- '()))
-
-(define (dequeue q)
- (if (null? (car q))
- (dequeue (flush q))
- (cons (caar q)
- (cons (cdar q)
- (cdr q)))))
-
-(define (empty? q)
- (and (null? (car q))
- (null? (cdr q))))
-
-(define (peek q)
- (car (dequeue q)))
-
-(define (print-queue q)
- (define (rec l leading-space?)
- (when (not (null? l))
- (when leading-space?
- (display " "))
- (display (car l))
- (rec (cdr l) #t)))
-
- (display "#q(")
- (rec (car q) false)
- (rec (reverse (cdr q)) (not (null? (car q))))
- (display ")")
- (newline))
-----
-
-Sample interactive session:
-
-[source,scheme]
-----
-scheme@(guile-user)> (define true #t)
-scheme@(guile-user)> (define false #f)
-scheme@(guile-user)> (define q (queue))
-scheme@(guile-user)> (print-queue q)
-#q()
-scheme@(guile-user)> (print-queue (enqueue 'a q))
-#q(a)
-scheme@(guile-user)> (print-queue q)
-#q()
-scheme@(guile-user)> (set! q (enqueue 'a q))
-scheme@(guile-user)> (print-queue q)
-#q(a)
-scheme@(guile-user)> (set! q (enqueue 'e (enqueue 'd (enqueue 'c (enqueue 'b q)))))
-scheme@(guile-user)> (print-queue q)
-#q(e d c b a)
-scheme@(guile-user)> (peek q)
-$28 = a
-scheme@(guile-user)> (define ret (dequeue q))
-scheme@(guile-user)> (define value (car ret))
-scheme@(guile-user)> (set! q (cdr ret))
-scheme@(guile-user)> value
-$29 = a
-scheme@(guile-user)> (print-queue q)
-#q(b c d e)
-scheme@(guile-user)> (print-queue (cdr (dequeue (cdr (dequeue (enqueue 'g (enqueue 'f q)))))))
-#q(d e f g)
-----