aboutsummaryrefslogtreecommitdiff
path: root/src/content/pastebins/2021/09
diff options
context:
space:
mode:
Diffstat (limited to 'src/content/pastebins/2021/09')
-rw-r--r--src/content/pastebins/2021/09/02/sicp-3-19.adoc42
-rw-r--r--src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc85
2 files changed, 127 insertions, 0 deletions
diff --git a/src/content/pastebins/2021/09/02/sicp-3-19.adoc b/src/content/pastebins/2021/09/02/sicp-3-19.adoc
new file mode 100644
index 0000000..75ee346
--- /dev/null
+++ b/src/content/pastebins/2021/09/02/sicp-3-19.adoc
@@ -0,0 +1,42 @@
+---
+
+title: SICP exercise 3.19
+
+date: 2021-09-02
+
+layout: post
+
+lang: en
+
+ref: sicp-exercise-3-19
+
+---
+
+```scheme
+(define (cycle? l)
+ (define (rec l x)
+ (cond
+ ((null? x) false)
+ ((eq? l x) true)
+ (true (rec l (cdr x)))))
+ (rec l (cdr l)))
+```
+
+Sample interactive session:
+
+```scheme
+scheme@(guile-user)> (define true #t)
+scheme@(guile-user)> (define false #f)
+scheme@(guile-user)>
+(define (cycle? l)
+ (define (rec l x)
+ (cond
+ ((null? x) false)
+ ((eq? l x) true)
+ (true (rec l (cdr x)))))
+ (rec l (cdr l)))
+scheme@(guile-user)> (cycle? '(1 2 3))
+$9 = #f
+scheme@(guile-user)> (cycle? (make-cycle '(1 2 3)))
+$10 = #t
+```
diff --git a/src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc b/src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc
new file mode 100644
index 0000000..8cf7ea2
--- /dev/null
+++ b/src/content/pastebins/2021/09/03/sicp-persistent-queue.adoc
@@ -0,0 +1,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)
+```