public
Created

Applicative-Order Y Combinator (Clojure Version)

  • Download Gist
ycombinator.clj
Clojure
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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
; Stumbling towards Y (Clojure Version)
;
; (this tutorial can be cut & pasted into your IDE / editor)
;
; The applicative-order Y combinator is a function that allows one to create a
; recursive function without using define.
; This may seem strange, because usually a recursive function has to call
; itself, and thus relies on itself having been defined.
;
; Regardless, here we will stumble towards the implementation of the Y combinator.
; This was largely influenced by material in "The Little Schemer".
; http://www.ccs.neu.edu/home/matthias/BTLS/
;
; I wrote this because I needed the excersise of arriving at Y on my own terms.
; As such, it is likely not the best resource to learn this.
;
; Mark Bolusmjak 2009
(def else true)
; Let's start with the Factorial function.
(def fact
(fn [n]
(cond
(= 0 n) 1
else (* n (fact (- n 1))))))
; Since we can't use define, let's strip that off.
; For the recursive call, let's just put in a placeholder
; to see how things look. (commented out because it won't compile)
(comment
(fn [n]
(cond
(= 0 n) 1
else (* n (myself (- n 1))))))
; Ok, we need a way for the function to call itself via "myself".
; How will we get a handle on that if we can't use define?
; Maybe something can pass it in for us. Let's hope so and
; keep going.
(fn [myself]
(fn [n]
(cond
(= 0 n) 1
else (* n (myself (- n 1))))))
; That looks a lot like our original factorial function.
; Let's replace "myself" with fact and take a look (below).
;
; From the outside, it looks like something that makes the factorial function.
; Strangely, this function that creates the factorial function, relies on the
; function "fact" to be supplied to itself.
; Where will that come from? Does't that bring us back to square one?
(fn [fact]
(fn [n]
(cond
(= 0 n) 1
else (* n (fact (- n 1))))))
; Well, we have a function that builds the factorial function. That seems
; nearly as useful as a factorial function. Maybe we could pass that to itself
; and try to work with that.
; It's pretty easy to pass a function to itself if we have it defined.
; e.g. (f f)
; What about an anonymous function?
; No problem, just write a helper function that takes any function and applies
; it to itself.
(fn [f] (f f))
; Ok, let's throw that in and take a look.
; We'll pass fact to itself
((fn [f] (f f))
(fn [fact]
(fn [n]
(cond
(= 0 n) 1
else (* n (fact (- n 1)))))))
; What happens if we try this out?
(((fn [f] (f f))
(fn [fact]
(fn [n]
(cond
(= 0 n) 1
else (* n (fact (- n 1))))))) 0)
; Hey it works for 0, but not for anything else.
; What's going on?
;
; With 0, (= 0 n) is true, and we get 1 back.
;
; If we try any other number we get a ClassCastException. Huh?
; We got a bit ahead of ourselves.
; Recall, fact is not the factorial funtion anymore. It now *builds* the
; factorial function.
; Also, we set it up to expecting a function as an argument before it returns
; the actual function we want.
;
; This may be getting strange, but let's try to make a useful function out of
; fact by calling (fact fact). This is good for one more step into our
; function, at which point (fact fact) can be used again to get the next step.
(((fn [f] (f f))
(fn [fact]
(fn [n]
(cond
(= 0 n) 1
else (* n ((fact fact) (- n 1))))))) 5)
; Wow! That actually worked.
; Take a breather and think about this for a second. We took a few shots in the
; dark and just implemented a recursive function without using define.
; Pretty cool, but it's kind of messy.
;
; We have something that kind of looks like our original factorial definition
; in there. Let's try to refactor that out and see what we're left with.
;
; Our original fact function didn't have anything looking like a (fact fact) in
; it, so let's try to fix that first.
;
; As the next step, we'll pull out the (fact fact) and give it a name.
; What should we call it?
; fact is kind of like factorial builder at this point, so (fact fact) is more
; like the factorial function.
; Hmm ... let's just call (fact fact) fact2, see how things look and go from
; there.
;
; We're going to be clever and instead of simply passing (fact fact) in as fact2,
; were going to wrap it up as a closure to prevent (fact fact) from getting
; evaluated before it gets passed in.
;
; So we'll pass in (fn [x] ((fact fact) x)) instead.
((fn [f] (f f))
(fn [fact]
((fn [fact2]
(fn [n]
(cond
(= 0 n) 1
else (* n (fact2 (- n 1)))))) (fn [x] ((fact fact) x)))))
; If we try this out, we see it still works.
(((fn [f] (f f))
(fn [fact]
((fn [fact2]
(fn [n]
(cond
(= 0 n) 1
else (* n (fact2 (- n 1)))))) (fn [x] ((fact fact) x))))) 12)
; Taking a closer look, we see that (fn [fact2] ... ) looks exactly like
; our original (fn (fact) ... ).
; Let's simply rename fact to y, and fact2 to fact to make this more clear.
((fn [f] (f f))
(fn [y]
((fn [fact]
(fn [n]
(cond
(= 0 n) 1
else (* n (fact (- n 1)))))) (fn [x] ((y y) x)))))
; Let's pull out (fn [fact] ... ) and pass it in as a parameter r (for
; recursive function).
((fn [r]
((fn [f] (f f))
(fn [y]
(r (fn [x] ((y y) x))))))
(fn [fact]
(fn [n]
(cond
(= 0 n) 1
else (* n (fact (- n 1)))))))
; Still works! Try it.
(((fn [r]
((fn [f] (f f))
(fn [y]
(r (fn [x] ((y y) x))))))
(fn [fact]
(fn [n]
(cond
(= 0 n) 1
else (* n (fact (- n 1))))))) 4)
; Now we've isolated the scaffolding we've built to allow the creation of a
; recursive function without define.
;
; Finally, we've lived long enough without define, and that thing we built
; looks pretty useful.
; Let's use define and call it Y.
(def Y
(fn [r]
((fn [f] (f f))
(fn [y]
(r (fn [x] ((y y) x)))))))
; That's it. We've built the applicative-order Y combinator in Clojure.
; Try it with another recursive function. Here it is with the Fibonacci
; number generator.
; (which, incidentally, makes 2 recursive calls to itself).
((Y
(fn [fib]
(fn [n]
(cond
(< n 2) n
else (+ (fib (- n 1)) (fib (- n 2))))))) 8)

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.