diff options
Diffstat (limited to '_pastebins/2021-09-03-sicp-persistent-on-queue.md')
-rw-r--r-- | _pastebins/2021-09-03-sicp-persistent-on-queue.md | 85 |
1 files changed, 0 insertions, 85 deletions
diff --git a/_pastebins/2021-09-03-sicp-persistent-on-queue.md b/_pastebins/2021-09-03-sicp-persistent-on-queue.md deleted file mode 100644 index e00b9d7..0000000 --- a/_pastebins/2021-09-03-sicp-persistent-on-queue.md +++ /dev/null @@ -1,85 +0,0 @@ ---- - -title: SICP persistent O(n) queue - -date: 2021-09-03 - -layout: post - -lang: en - -ref: sicp-persistent-on-queue - ---- - -```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: -```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) -``` |