135 lines
3.3 KiB
Scheme
135 lines
3.3 KiB
Scheme
|
|
;; I am not drawing box-and-pointer diagrams lmao
|
|
;; still, to answer 3.12:
|
|
|
|
;; first:
|
|
;; (cdr x)
|
|
;; => '(b)
|
|
;; because x is not modified in the call to append
|
|
|
|
;; however, append! modifies the underlying data structure
|
|
;; held in x, hence the second (cdr x) returns:
|
|
;; => '(b c d)
|
|
|
|
(define (append! x y)
|
|
(set-cdr! (last-pair x) y)
|
|
x)
|
|
|
|
(define (last-pair x)
|
|
(if (null? (cdr x)) x (last-pair (cdr x))))
|
|
|
|
;; don't run these twice, you'll create a circular list.
|
|
;; I lost a good many REPL's to this.
|
|
(define x '(a b))
|
|
(define y '(c d))
|
|
(append! x y)
|
|
x ; => '(a b c d)
|
|
(cdr x) ; => '(b c d)
|
|
|
|
|
|
;; 3.13:
|
|
;; oh! how very nice - a question about the very thing I just
|
|
;; wrote about.
|
|
|
|
;; the REPL hangs. It tries to traverse to the end of a list
|
|
;; that doesn't have an end. Like most human lives, it dies
|
|
;; a meaningless death in search of that which does not exist,
|
|
;; a search that goes round and round and round forever.
|
|
|
|
;; I.e. we constructed a cyclical list.
|
|
|
|
;; 3.14:
|
|
;; This is a list reversal procedure.
|
|
;; The input list is destructively reversed in-place, i.e. with
|
|
;; no allocations.
|
|
|
|
;; v will still refer to the same cons cell, so its value is
|
|
;; '(a)
|
|
;; w will refer to the new head of the (now-reversed) list.
|
|
;; '(d c b a)
|
|
|
|
(define (mystery x)
|
|
(define (loop x y)
|
|
(if (null? x)
|
|
y
|
|
(let ((temp (cdr x)))
|
|
(set-cdr! x y)
|
|
(loop temp x))))
|
|
(loop x '()))
|
|
|
|
;; this procedure is useful because its sometimes very convenient
|
|
;; to generate data into a list through cons cells, then reverse
|
|
;; it at the end (through an efficient reversal procedure like this)
|
|
|
|
;; 3.16:
|
|
|
|
(define (count-pairs x)
|
|
(if (not (pair? x))
|
|
0
|
|
(+ (count-pairs (car x))
|
|
(count-pairs (cdr x))
|
|
1)))
|
|
|
|
(count-pairs '(a b c)) ; => 3
|
|
|
|
(define fourbase (cons 1 '()))
|
|
(define four (cons fourbase (cons fourbase '())))
|
|
(count-pairs four) ; => 4
|
|
|
|
(define sevenbase (cons 1 '()))
|
|
(define sevenmid (cons sevenbase sevenbase))
|
|
(define seven (cons sevenmid sevenmid))
|
|
(count-pairs seven) ; => 7
|
|
|
|
;; and for the great finale...
|
|
(define finale-a (cons 'a '()))
|
|
(define finale-b (cons 'b finale-a))
|
|
(define finale-c (cons 'c finale-b))
|
|
(set-cdr! finale-a finale-c)
|
|
;; (you can do this with a single cons cell, actually)
|
|
|
|
;; 3.17
|
|
;; it seems that eq? really does simply check for
|
|
;; pointer equality - if literally the same cons
|
|
;; cell is passed twice it returns #t but if two
|
|
;; cons cells with the same values are created
|
|
;; they measure #f.
|
|
|
|
;; it's honestly very convenient to know this
|
|
;; it simplifies and clarifies a lot of things.
|
|
|
|
;; we can use this to essentially build a list of
|
|
;; all pairs we have ever visited. We can have this
|
|
;; list behave like a set - which we defined before.
|
|
|
|
;; I used a hash table instead because they were available.
|
|
;; and efficient, I guess.
|
|
|
|
;; You can count the number of pairs without falling
|
|
;; for cycles by just refusing to traverse a cell
|
|
;; that has already been traversed, though this
|
|
;; requires extra storage.
|
|
;; I'm gonna count this for 3.18, as the logic
|
|
;; is incredibly similar.
|
|
|
|
|
|
(define (count-pairs-2 x)
|
|
(define table (make-eq-hashtable))
|
|
(define (mark-visited! c)
|
|
(set-cdr! (hashtable-cell table c #t) #t)
|
|
#t)
|
|
(define (visited? x)
|
|
(eq-hashtable-ref table x #f))
|
|
(define (loop x)
|
|
(when (and (pair? x) (not (visited? x)))
|
|
(mark-visited! x)
|
|
(loop (car x))
|
|
(loop (cdr x))))
|
|
(loop x)
|
|
(vector-length (hashtable-values table)))
|
|
|
|
|
|
|
|
|
|
|