1 ;; These are the answers to the questions in ../docs/exercise.md.
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))))))
13 (def! nil? (fn* [x] (= x nil )))
14 (def! true? (fn* [x] (= x true )))
15 (def! false? (fn* [x] (= x false)))
16 (def! empty? (fn* [x] (= x [] )))
20 (if (list? x) true (vector? x))))
22 (def! > (fn* [a b] (< b a) ))
23 (def! <= (fn* [a b] (not (< b a))))
24 (def! >= (fn* [a b] (not (< a b))))
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))))
35 (reduce (fn* [acc _] (+ 1 acc)) 0 xs))))
38 (if (if (<= 0 index) (not (empty? xs))) ; logical and
41 (nth (rest xs) (- index 1)))
42 (throw "nth: index out of range"))))
45 (foldr (fn* [x acc] (cons (f x) acc)) () xs)))
48 (foldr (fn* [xs ys] (foldr cons ys xs)) () xs)))
52 (apply vector (concat xs ys))
53 (reduce (fn* [xs x] (cons x xs)) xs ys))))
55 (def! do2 (fn* [& xs] (nth xs (- (count xs) 1))))
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.
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]
68 (if (= (first ast) 'unquote)
70 (foldr _quasiquote_iter () ast))
72 ;; TODO: once tests are fixed, replace 'list with 'vector.
73 (list 'apply 'list (foldr _quasiquote_iter () ast))
76 (def! _letA_keys (fn* [binds]
79 (cons (first binds) (_letA_keys (rest (rest binds)))))))
80 (def! _letA_values (fn* [binds]
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]
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))
93 (def! _c_combinator (fn* [x] (x x)))
94 (def! _d_combinator (fn* [f] (fn* [x] (f (fn* [v] ((x x) v))))))
95 (def! _Y_combinator (fn* [x] (_c_combinator (_d_combinator x))))
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)
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))
114 (if (nil? acc) ; x is the last element (a sequence)
117 (fn* [& xs] (eval (foldr iter nil xs)))))
121 (def! sum (fn* [xs] (reduce + 0 xs)))
122 (def! product (fn* [xs] (reduce * 1 xs)))
125 (let* [and2 (fn* [acc x] (if acc x false))]
127 (reduce and2 true xs))))
129 (let* [or2 (fn* [acc x] (if acc true x))]
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.
136 ;; Yes, -2-3-4 means (((0-2)-3)-4).
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.
142 ;; `(reduce (fn* [acc _] acc) nil xs)` is equivalent to `nil`.
144 ;; For (reduce (fn* [acc x] x) nil xs))), see do3 above.
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.
151 (let* [add_len (fn* [acc x] (+ acc (count x)))]
153 (reduce add_len 0 xs))))
155 (let* [update_max (fn* [acc x] (let* [l (count x)] (if (< acc l) l acc)))]
157 (reduce update_max 0 xs))))
160 (let* [compose2 (fn* [f acc] (fn* [x] (f (acc x))))]
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.