commit 628ab61366b9134104882076e95c6b9f3200a431
parent f7b93a4391a94ec25333c0f9dee972b3a1c6e4ec
Author: Yuval Langer <yuval.langer@gmail.com>
Date: Sun, 16 Apr 2023 11:41:05 +0300
Add more solutions.
Diffstat:
6 files changed, 316 insertions(+), 0 deletions(-)
diff --git a/sicp/solutions/3_12.scm b/sicp/solutions/3_12.scm
@@ -0,0 +1,16 @@
+(define-library (sicp solutions 3_12)
+ (import (scheme base))
+ (export
+ append!
+ last-pair
+ )
+
+ (begin
+ (define (last-pair x)
+ (cond
+ ((null? (cdr x)) x)
+ (else (last-pair (cdr x)))))
+
+ (define (append! x y)
+ (set-cdr! (last-pair x) y)
+ x)))
diff --git a/sicp/solutions/3_13.scm b/sicp/solutions/3_13.scm
@@ -0,0 +1,13 @@
+(define-library (sicp solutions 3_13)
+ (import (scheme base))
+ (export make-cycle)
+
+ (begin
+ (define (last-pair x)
+ (if (null? (cdr x))
+ x
+ (last-pair (cdr x))))
+
+ (define (make-cycle x)
+ (set-cdr! (last-pair x) x)
+ x)))
diff --git a/sicp/solutions/3_14.scm b/sicp/solutions/3_14.scm
@@ -0,0 +1,13 @@
+(define-library (sicp solutions 3_14)
+ (import (scheme base))
+ (export mystery)
+
+ (begin
+ (define (mystery x)
+ (define (loop x y)
+ (if (null? x)
+ y
+ (let ([temp (cdr x)])
+ (set-cdr! x y)
+ (loop temp x))))
+ (loop x '()))))
diff --git a/sicp/tests/3_12.scm b/sicp/tests/3_12.scm
@@ -0,0 +1,50 @@
+(define-library (sicp tests 3_12)
+ (import (scheme base))
+ (import (srfi :64))
+ (import (only (sicp solutions 3_12) append!))
+
+ (begin
+ (define x (list 'a 'b))
+ (define y (list 'c 'd))
+ (define z (append x y))
+
+ ;; x: ['a | -]-> ['b | '()]
+ ;; y: ['c | -]-> ['d | '()]
+ ;; ^
+ ;; |
+ ;; +----------------+
+ ;; |
+ ;; z: ['a | -]-> ['b | -]--+
+
+ (test-begin "3.12")
+ (test-equal
+ '(a b c d)
+ z)
+ (test-equal
+ '(b)
+ (cdr x))
+ (define w (append! x y))
+
+ ;; +-------------------+
+ ;; | |
+ ;; v |
+ ;; x: ['a | -]-> ['b | -]--+ |
+ ;; | |
+ ;; +----------------+ |
+ ;; | |
+ ;; V |
+ ;; y: ['c | -]-> ['d | '()] |
+ ;; ^ |
+ ;; | |
+ ;; +----------------+ |
+ ;; | |
+ ;; z: ['a | -]-> ['b | -]--+ |
+ ;; w: ------------------------+
+
+ (test-equal
+ '(a b c d)
+ w)
+ (test-equal
+ '(b c d)
+ (cdr x))
+ (test-end "3.12")))
diff --git a/sicp/tests/3_13.scm b/sicp/tests/3_13.scm
@@ -0,0 +1,12 @@
+(define-library (sicp tests 3_13)
+ (import (scheme base))
+ (import (only (srfi :1) last-pair))
+ (import (srfi :64))
+ (import (only (sicp solutions 3_13) make-cycle))
+
+ (begin
+ (define z (make-cycle (list 'a 'b 'c)))
+
+ (test-begin "3.13")
+ (test-error (last-pair z)) ; Guile's last-pair checks for and raises an error on cyclic lists.
+ (test-end "3.13")))
diff --git a/sicp/tests/3_14.scm b/sicp/tests/3_14.scm
@@ -0,0 +1,212 @@
+(define-library (sicp tests 3_14)
+ (import (scheme base))
+ (import (srfi :64))
+
+ (begin
+ (test-begin "3.14")
+
+ (define v '(a b c d))
+
+ ;; v: [a|-]-> [b|-]-> [c|-]-> [d|()]
+
+ ;; iteration 1
+ (define y '()) (define x v)
+ ;; v: [a|-]-> [b|-]-> [c|-]-> [d|()]
+ ;; ^
+ ;; |
+ ;; x: --+
+ ;; y: ()
+ (test-equal '(a b c d) x)
+ (test-equal '() y)
+
+ (define temp (cdr x))
+ ;; v: [a|-]-> [b|-]-> [c|-]-> [d|()]
+ ;; ^ ^
+ ;; | |
+ ;; x: --+ |
+ ;; y: () |
+ ;; temp: -------+
+ (test-equal '(b c d) temp)
+
+ (set-cdr! x y)
+ ;; v: [a|()] [b|-]-> [c|-]-> [d|()]
+ ;; ^ ^
+ ;; | |
+ ;; x: --+ |
+ ;; y: () |
+ ;; temp: -------+
+ (test-equal '(a) x)
+
+ ;; iteration 2
+ (define y x) (define x temp)
+ ;; v: [a|()] [b|-]-> [c|-]-> [d|()]
+ ;; ^ ^
+ ;; | |
+ ;; +-+ |
+ ;; | |
+ ;; +------+
+ ;; | | |
+ ;; x: --+ | |
+ ;; y: ----+ |
+ ;; temp: ------+
+ (test-equal '(b c d) x)
+ (test-equal '(a) y)
+
+ (define temp (cdr x))
+ ;; v: [a|()] [b|-]-> [c|-]-> [d|()]
+ ;; ^ ^ ^
+ ;; | | |
+ ;; +-+ | |
+ ;; | | |
+ ;; +------+ |
+ ;; | | |
+ ;; x: --+ | |
+ ;; y: ----+ |
+ ;; temp: --------------+
+ (test-equal '(c d) temp)
+
+ (set-cdr! x y)
+ ;; +----------+
+ ;; | |
+ ;; V |
+ ;; v: [a|()] [b|-]-+ [c|-]-> [d|()]
+ ;; ^ ^ ^
+ ;; | | |
+ ;; +-+ | |
+ ;; | | |
+ ;; +------+ |
+ ;; | | |
+ ;; x: --+ | |
+ ;; y: ----+ |
+ ;; temp: --------------+
+ (test-equal '(b a) x)
+
+ ;; iteration 3
+ (define y x) (define x temp)
+ ;; +----------+
+ ;; | |
+ ;; V |
+ ;; v: [a|()] [b|-]-+ [c|-]-> [d|()]
+ ;; ^ ^
+ ;; | |
+ ;; +--------------+
+ ;; | | |
+ ;; | +----+ |
+ ;; | | |
+ ;; x: --+ | |
+ ;; y: ----+ |
+ ;; temp: --------------+
+ (test-equal '(c d) x)
+ (test-equal '(b a) y)
+
+ (define temp (cdr x))
+ ;; +----------+
+ ;; | |
+ ;; V |
+ ;; v: [a|()] [b|-]-+ [c|-]-> [d|()]
+ ;; ^ ^ ^
+ ;; | | |
+ ;; +--------------+ |
+ ;; | | |
+ ;; | +----+ |
+ ;; | | |
+ ;; x: --+ | |
+ ;; y: ----+ |
+ ;; temp: ----------------------+
+ (test-equal '(d) temp)
+
+ (set-cdr! x y)
+ ;; +-----------+
+ ;; | |
+ ;; +----------+ |
+ ;; | | | |
+ ;; V V | |
+ ;; v: [a|()] [b|-]-+ [c|-]-+ [d|()]
+ ;; ^ ^ ^
+ ;; | | |
+ ;; +--------------+ |
+ ;; | | |
+ ;; | +----+ |
+ ;; | | |
+ ;; x: --+ | |
+ ;; y: ----+ |
+ ;; temp: ----------------------+
+ (test-equal '(c b a) x)
+
+ ;; iteration 4
+ (define y x) (define x temp)
+ ;; +-----------+
+ ;; | |
+ ;; +----------+ |
+ ;; | | | |
+ ;; V V | |
+ ;; v: [a|()] [b|-]-+ [c|-]-+ [d|()]
+ ;; ^ ^
+ ;; | |
+ ;; +------------+ |
+ ;; | |
+ ;; +----------------------+
+ ;; | | |
+ ;; x: --+ | |
+ ;; y: ----+ |
+ ;; temp: ----------------------+
+ (test-equal '(d) x)
+ (test-equal '(c b a) y)
+
+ (define temp (cdr x))
+ ;; +-----------+
+ ;; | |
+ ;; +----------+ |
+ ;; | | | |
+ ;; V V | |
+ ;; v: [a|()] [b|-]-+ [c|-]-+ [d|()]
+ ;; ^ ^ ^
+ ;; | | |
+ ;; +------------+ | |
+ ;; | | |
+ ;; +----------------------+ |
+ ;; | | |
+ ;; x: --+ | |
+ ;; y: ----+ |
+ ;; temp: ------------------------+
+ (test-equal '() temp)
+
+ (set-cdr! x y)
+ ;; +-----------+
+ ;; | |
+ ;; +----------+ +-----------+
+ ;; | | | | | |
+ ;; V V | V | |
+ ;; v: [a|()] [b|-]-+ [c|-]-+ [d|-]-+
+ ;; ^ ^
+ ;; | | ()
+ ;; +------------+ | ^
+ ;; | | |
+ ;; +----------------------+ |
+ ;; | | |
+ ;; x: --+ | |
+ ;; y: ----+ |
+ ;; temp: ------------------------+
+ (test-equal '(d c b a) x)
+
+ ;; iteration 5
+ (define y x) (define x temp)
+ ;; +-----------+
+ ;; | |
+ ;; +----------+ +-----------+
+ ;; | | | | | |
+ ;; V V | V | |
+ ;; v: [a|()] [b|-]-+ [c|-]-+ [d|-]-+
+ ;; ^
+ ;; | ()
+ ;; | ^
+ ;; | |
+ ;; +--------------------+ |
+ ;; | |
+ ;; x: ----|----------------------+
+ ;; y: ----+ |
+ ;; temp: ------------------------+
+ (test-equal '() x)
+ (test-equal '(d c b a) y)
+ (test-equal '(a) v)
+ (test-end "3.14")))
