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
76
77
78
79
80
81
82
83
84
85
86
87
|
; Copyright (c) 1993-2008 by Richard Kelsey. See file COPYING.
(define-data-type list
(pair? (cons car cdr)
(car integer car set-car!)
(cdr list cdr set-cdr!))
(null? null))
; Also want pair->list (but probably not null->list).
; That means that PAIR is a separate type, which is not what ML does.
; Does the constructor make a pair or a list? Two constructors?
; The minimal version needs the pair-maker and pair->list.
(define-data-type list
(pair pair->list
(make-pair car cdr)
(car integer car set-car!)
(cdr list cdr set-cdr!))
(null))
(define (cons x y)
(pair->list (make-pair x y)))
; Could write it this way from scratch.
(define-record-type :pair
(make-pair car cdr)
(car integer car set-car!)
(cdr list cdr set-cdr!))
(define-data-type :list
(pair :pair)
(null? null))
; pair->list needs to cons, especially if there are multiple options.
; This does show that the basic idea is sound - only the implementation
; changes from ML. Polymorphic lists would be tough this way.
(define (member? list x)
(let loop ((list list))
(cond ((null? list)
#f)
((= x (car list))
#t)
(else
(loop (cdr list))))))
(define (member? list x)
(let loop ((list list))
(delistify list
((null)
#f)
((pair head tail)
(if (= x head)
#t
(loop tail))))))
(define (reverse! list)
(if (or (null? list)
(null? (cdr list)))
list
(let loop ((list list) (prev null))
(let ((next (cdr list)))
(set-cdr! list prev)
(if (null? next)
list
(loop next list))))))
; Not terrible.
(define (reverse! list)
(delistify list
((null)
list)
((pair . first-pair)
(delistify (cdr first-pair)
((null)
list)
((pair)
(let loop ((pair first-pair) (prev null))
(let ((next (cdr pair)))
(set-cdr! pair prev)
(delistify next
((null)
pair)
((pair . next-pair)
(loop next-pair next))))))))))
|
