Commit | Line | Data |
---|---|---|
0544b52f NB |
1 | ;; These are the answers to the questions in ../docs/exercise.md. |
2 | ||
9c20ca3f NB |
3 | ;; In order to avoid unexpected circular dependencies among solutions, |
4 | ;; this files attempts to be self-contained. | |
5 | (def! identity (fn* [x] x)) | |
6 | (def! reduce (fn* (f init xs) | |
7 | (if (empty? xs) init (reduce f (f init (first xs)) (rest xs))))) | |
8 | (def! foldr (fn* [f init xs] | |
9 | (if (empty? xs) init (f (first xs) (foldr f init (rest xs)))))) | |
10 | ||
11 | ;; Reimplementations. | |
1ca3ee3d | 12 | |
0544b52f NB |
13 | (def! nil? (fn* [x] (= x nil ))) |
14 | (def! true? (fn* [x] (= x true ))) | |
15 | (def! false? (fn* [x] (= x false))) | |
9678065e | 16 | (def! empty? (fn* [x] (= x [] ))) |
0544b52f | 17 | |
9678065e NB |
18 | (def! sequential? |
19 | (fn* [x] | |
9c20ca3f | 20 | (if (list? x) true (vector? x)))) |
0544b52f | 21 | |
9678065e NB |
22 | (def! > (fn* [a b] (< b a) )) |
23 | (def! <= (fn* [a b] (not (< b a)))) | |
24 | (def! >= (fn* [a b] (not (< a b)))) | |
0544b52f NB |
25 | |
26 | (def! hash-map (fn* [& xs] (apply assoc {} xs))) | |
27 | (def! list (fn* [& xs] xs)) | |
28 | (def! prn (fn* [& xs] (println (apply pr-str xs)))) | |
29 | (def! swap! (fn* [a f & xs] (reset! a (apply f (deref a) xs)))) | |
30 | ||
1ca3ee3d | 31 | (def! count |
9c20ca3f NB |
32 | (fn* [xs] |
33 | (if (nil? xs) | |
34 | 0 | |
35 | (reduce (fn* [acc _] (+ 1 acc)) 0 xs)))) | |
36 | (def! nth | |
37 | (fn* [xs index] | |
38 | (if (if (<= 0 index) (not (empty? xs))) ; logical and | |
39 | (if (= 0 index) | |
40 | (first xs) | |
41 | (nth (rest xs) (- index 1))) | |
42 | (throw "nth: index out of range")))) | |
0544b52f NB |
43 | (def! map |
44 | (fn* [f xs] | |
9c20ca3f | 45 | (foldr (fn* [x acc] (cons (f x) acc)) () xs))) |
1ca3ee3d | 46 | (def! concat |
9c20ca3f NB |
47 | (fn* [& xs] |
48 | (foldr (fn* [xs ys] (foldr cons ys xs)) () xs))) | |
1ca3ee3d | 49 | (def! conj |
9c20ca3f NB |
50 | (fn* [xs & ys] |
51 | (if (vector? xs) | |
52 | (apply vector (concat xs ys)) | |
53 | (reduce (fn* [xs x] (cons x xs)) xs ys)))) | |
0544b52f | 54 | |
9c20ca3f | 55 | (def! do2 (fn* [& xs] (nth xs (- (count xs) 1)))) |
9678065e NB |
56 | (def! do3 (fn* [& xs] (reduce (fn* [acc x] x) nil xs))) |
57 | ;; do2 will probably be more efficient when lists are implemented as | |
58 | ;; arrays with direct indexing, but when they are implemented as | |
59 | ;; linked lists, do3 may win because it only does one traversal. | |
0544b52f | 60 | |
9c20ca3f NB |
61 | (defmacro! quote (fn* [ast] (list (fn* [] ast)))) |
62 | (def! _quasiquote_iter (fn* [x acc] | |
63 | (if (if (list? x) (= (first x) 'splice-unquote)) ; logical and | |
64 | (list 'concat (first (rest x)) acc) | |
65 | (list 'cons (list 'quasiquote x) acc)))) | |
66 | (defmacro! quasiquote (fn* [ast] | |
67 | (if (list? ast) | |
68 | (if (= (first ast) 'unquote) | |
69 | (first (rest ast)) | |
70 | (foldr _quasiquote_iter () ast)) | |
71 | (if (vector? ast) | |
72 | ;; TODO: once tests are fixed, replace 'list with 'vector. | |
73 | (list 'apply 'list (foldr _quasiquote_iter () ast)) | |
74 | (list 'quote ast))))) | |
75 | ||
0f37b1af NB |
76 | (def! _letA_keys (fn* [binds] |
77 | (if (empty? binds) | |
78 | () | |
79 | (cons (first binds) (_letA_keys (rest (rest binds))))))) | |
80 | (def! _letA_values (fn* [binds] | |
81 | (if (empty? binds) | |
82 | () | |
83 | (_letA_keys (rest binds))))) | |
84 | (def! _letA (fn* [binds form] | |
85 | (cons (list 'fn* (_letA_keys binds) form) (_letA_values binds)))) | |
86 | ;; Fails for (let* [a 1 b (+ 1 a)] b) | |
87 | (def! _letB (fn* [binds form] | |
88 | (if (empty? binds) | |
89 | form | |
90 | (list (list 'fn* [(first binds)] (_letB (rest (rest binds)) form)) | |
91 | (first (rest binds)))))) | |
92 | ;; Fails for (let* (cst (fn* (n) (if (= n 0) nil (cst (- n 1))))) (cst 1)) | |
9c20ca3f NB |
93 | (def! _c_combinator (fn* [x] (x x))) |
94 | (def! _d_combinator (fn* [f] (fn* [x] (f (fn* [v] ((x x) v)))))) | |
0f37b1af NB |
95 | (def! _Y_combinator (fn* [x] (_c_combinator (_d_combinator x)))) |
96 | (def! _letC | |
0544b52f NB |
97 | (fn* [binds form] |
98 | (if (empty? binds) | |
99 | form | |
0f37b1af NB |
100 | (list (list 'fn* [(first binds)] (_letC (rest (rest binds)) form)) |
101 | (list '_Y_combinator (list 'fn* [(first binds)] (first (rest binds)))))))) | |
102 | ;; Fails for mutual recursion. | |
103 | ;; See http://okmij.org/ftp/Computation/fixed-point-combinators.html | |
104 | ;; if you are motivated to implement solution D. | |
105 | (defmacro! let* _letC) | |
7977c2cb | 106 | |
304930e7 | 107 | (def! apply |
1ca3ee3d NB |
108 | ;; Replace (f a b [c d]) with ('f 'a 'b 'c 'd) then evaluate the |
109 | ;; resulting function call (the surrounding environment does not | |
110 | ;; matter when evaluating a function call). | |
111 | ;; Use nil as marker to detect deepest recursive call. | |
112 | (let* [q (fn* [x] (list 'quote x)) | |
113 | iter (fn* [x acc] | |
114 | (if (nil? acc) ; x is the last element (a sequence) | |
115 | (map q x) | |
116 | (cons (q x) acc)))] | |
117 | (fn* [& xs] (eval (foldr iter nil xs))))) | |
9678065e | 118 | |
9c20ca3f NB |
119 | ;; Folds |
120 | ||
9678065e NB |
121 | (def! sum (fn* [xs] (reduce + 0 xs))) |
122 | (def! product (fn* [xs] (reduce * 1 xs))) | |
123 | ||
124 | (def! conjunction | |
125 | (let* [and2 (fn* [acc x] (if acc x false))] | |
126 | (fn* [xs] | |
127 | (reduce and2 true xs)))) | |
128 | (def! disjunction | |
129 | (let* [or2 (fn* [acc x] (if acc true x))] | |
130 | (fn* [xs] | |
131 | (reduce or2 false xs)))) | |
132 | ;; It would be faster to stop the iteration on first failure | |
133 | ;; (conjunction) or success (disjunction). Even better, `or` in the | |
134 | ;; stepA and `and` in `core.mal` stop evaluating their arguments. | |
135 | ||
136 | ;; Yes, -2-3-4 means (((0-2)-3)-4). | |
137 | ||
138 | ;; `(reduce str "" xs)` is equivalent to `apply str xs` | |
139 | ;; and `(reduce concat () xs)` is equivalent to `apply concat xs`. | |
140 | ;; The built-in iterations are probably faster. | |
141 | ||
142 | ;; `(reduce (fn* [acc _] acc) nil xs)` is equivalent to `nil`. | |
143 | ||
144 | ;; For (reduce (fn* [acc x] x) nil xs))), see do3 above. | |
145 | ||
146 | ;; `(reduce (fn* [acc x] (if (< acc x) x acc)) 0 xs)` computes the | |
147 | ;; maximum of a list of non-negative integers. It is hard to find an | |
148 | ;; initial value fitting all purposes. | |
149 | ||
150 | (def! sum_len | |
151 | (let* [add_len (fn* [acc x] (+ acc (count x)))] | |
152 | (fn* [xs] | |
9c20ca3f | 153 | (reduce add_len 0 xs)))) |
9678065e NB |
154 | (def! max_len |
155 | (let* [update_max (fn* [acc x] (let* [l (count x)] (if (< acc l) l acc)))] | |
156 | (fn* [xs] | |
157 | (reduce update_max 0 xs)))) | |
158 | ||
159 | (def! compose | |
160 | (let* [compose2 (fn* [f acc] (fn* [x] (f (acc x))))] | |
161 | (fn* [& fs] | |
162 | (foldr compose2 identity fs)))) | |
163 | ;; ((compose f1 f2) x) is equivalent to (f1 (f2 x)) | |
164 | ;; This is the mathematical composition. For practical purposes, `->` | |
165 | ;; and `->>` defined in `core.mal` are more efficient and general. |