blob: 902cc12ba334638727bf510a2498fd210ba8e30a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#lang racket
;; 12
(require compatibility/mlist)
(define (last-pair x)
(if (null? (mcdr x))
x
(last-pair (mcdr x))))
(define x (mlist 'a 'b))
(define y (mlist 'c 'd))
(define z (mappend x y))
x
(define w (mappend! x y))
x
;; 13
(define (make-cycle x)
(set-mcdr! (last-pair x) x)
x)
(define zp (make-cycle (mlist 'a 'b 'c)))
zp
;; last-pair would make an infinite loop
;; 14
;; The procedure reverses the list. And messes up the list that is bound in the global env
(define v (mlist 'a 'b 'c 'd))
(define (mystery x)
(define (loop x y)
(if (null? x)
y
(let ((temp (mcdr x)))
(set-mcdr! x y)
(loop temp x))))
(loop x '()))
(define wp (mystery v))
v
wp
;; 15
;; 16
;; 17
(define (make-pair-counter)
(define counted (list))
(define (count-pairs x)
(display counted)
(if (or (not (pair? x))
(memq x counted))
0
(begin
(set! counted (cons x counted))
(+ 1
(count-pairs (car x))
(count-pairs (cdr x))))))
count-pairs)
((make-pair-counter) (list 'a 'b 'c))
(define bc (list 'b 'c))
((make-pair-counter) (cons bc bc))
((make-pair-counter) (cons bc (cdr bc)))
(define c (list 'c))
(define b (cons c c))
((make-pair-counter) (cons b b))
;; 18/19
;; This is actually only a valid way to check for cycles if the first pair in the list is also the state of the cycle.
;; A better way would be to check against all memory addresses in the list by hashing or counting.
(define (cycle? x)
(define (iter v items)
(cond ((null? items) false)
((eq? v items) true)
(else (iter v (mcdr items)))))
(iter x (mcdr x)))
(cycle? (mlist 'a 'b 'c))
(cycle? (make-cycle (mlist 'a 'b 'c)))
;; For 19 you need a famous trick with two pointers
;; 20
|
