ycombinator.clj

;;; 01/14/14  16:18 by miner -- Steve Miner revised this code to be more idiomatic Clojure.
;;;

; Short sidebar: Clojure has a special form for the efficient compilation of tail recursion.
; Something like this would work as a factorial function:
(defn fact2 [n]
  (loop [n n acc 1]
    (if (zero? n) acc (recur (dec n) (* n acc)))))

; We're not going to discuss `recur` any further as we're imagining a language that doesn't
; support recursion for the rest of this demonstration.

; As far as the factorial itself, a good non-recursive implementation would be:
(defn fact3 [n]
  (reduce * (range 1 (inc n))))

; Again, we're using factorial just as an example of something you might want to implement using
; recursion.  So back to our story...



;;; Original comments:

;                    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 

;;; END original comments




 
; Let's start with the Factorial function. 
(defn fact1 [n] 
  (if (zero? n) 1 (* n (fact1 (dec n)))))

; Which is just short-hand for:
(def fact1 (fn [n] (if (zero? n) 1 (* n (fact1 (dec n))))))
 
; Since we can't use def, 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] 
    (if (zero? n) 1 (* n (myself (dec n))))))
   
; 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] 
    (if (zero? n) 1 (* n (myself (dec n))))))
 
; 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] (if (zero? n) 1 (* n (fact (dec n))))))

 
; 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] (if (zero? n) 1 (* n (fact (dec n)))))))
 
; What happens if we try this out? 
(((fn [f] (f f)) 
  (fn [fact] 
    (fn [n] (if (zero? n) 1 (* n (fact (dec n)))))))
 0)
;=> 1
 
; Hey it works for 0, but not for anything else. 
; What's going on? 
; 
; With 0, (zero? 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] 
      (if (zero? n) 1 (* n ((fact fact) (- n 1))))))) 5)
;=> 120

; 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] 
        (if (zero? n) 1 (* n (fact2 (dec n)))))) (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] 
        (if (zero? n) 1 (* n (fact2 (dec n)))))) (fn [x] ((fact fact) x)))))  12)
;=> 479001600

; 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] 
        (if (zero? n) 1 (* n (fact (dec n)))))) (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] 
      (if (zero? n) 1 (* n (fact (dec n)))))))
 
; Still works! Try it. 
(((fn [r] 
  ((fn [f] (f f)) 
    (fn [y] 
      (r (fn [x] ((y y) x)))))) 
  (fn [fact] 
    (fn [n] 
      (if (zero? n) 1 (* n (fact (dec n)))))))  4)
;=> 24

; 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] 
      (if (< n 2) n (+ (fib (dec n)) (fib (- n 2))))))) 8)
;=> 21