;; 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)))