From 1f787eb6a51a4ba38f026dc2f4872a92fca1175b Mon Sep 17 00:00:00 2001
From: EuAndreh <eu@euandre.org>
Date: Fri, 10 Sep 2021 09:29:30 -0300
Subject: Pastebin: O(n) -> amortized O(1)

---
 ...021-09-03-sicp-persistent-amortized-o1-queue.md | 85 ++++++++++++++++++++++
 _pastebins/2021-09-03-sicp-persistent-on-queue.md  | 85 ----------------------
 2 files changed, 85 insertions(+), 85 deletions(-)
 create mode 100644 _pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md
 delete mode 100644 _pastebins/2021-09-03-sicp-persistent-on-queue.md

diff --git a/_pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md b/_pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md
new file mode 100644
index 0000000..8cf7ea2
--- /dev/null
+++ b/_pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md
@@ -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)
+```
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)
-```
-- 
cgit v1.2.3