aboutsummaryrefslogtreecommitdiff
path: root/_pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md
blob: 8cf7ea26c907c1705d31ed2c97cf2ccbda7c4b81 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
---

title: SICP persistent amortized O(1) queue

date: 2021-09-03

layout: post

lang: en

ref: sicp-persistent-amortized-o1-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)
```