Wednesday, 22 April 2009
Understanding the Y Combinator
Like monads, understanding the Y Combinator is a rite of passage for the aspiring functional programmer. So here's my take on it, using Clojure.
A fixed point combinator is a function g which produces such a fixed point p for any function f.
Why is this important or interesting for a programming language? It's important because it allows you to describe recursion in terms of rewrites, rather than computation steps. This allows for anonymous recursive functions.
So how do we write the Y combinator in Clojure? Taking the lambda-calculus definition and switching the word
But what does it actually mean? Probably the best way to understand is with a real example and to do that, we need a recursive function. Given that everyone else uses factorial, we'll use a simpler recursive function that sums up a sequence.
In the definition above, we've written the function with explicit recursion. We'll use the Y combinator to get rid of that!
The first step is to rethink the function in terms of a series of functions. Our goal is to create a way of expressing this computation as a series of function calls. We want to write a function that given a function to compute the sum of a sequence, gives us the next function to compute the sum of a sequence.
So now we have such a function. We can already use it:
It's not that useful, as at the moment we'd have to type in an awful lot of characters to sum a large list. What we really want is some way of calculating the fixed point of such a function. Thankfully we already have that, thanks to the Y combinator.
So the Y Combinator has given us what we need. Given a function and an input, find the fixed point. Note that there is no explicit recursion going on.
The best way to understand the Y combinator is to see how it's used and then run through the fun exercise of expanding it and seeing what happens. I found the links below useful:
A fixed point combinator is a function g which produces such a fixed point p for any function f.
g(f)=p
f(p)=p
Why is this important or interesting for a programming language? It's important because it allows you to describe recursion in terms of rewrites, rather than computation steps. This allows for anonymous recursive functions.
So how do we write the Y combinator in Clojure? Taking the lambda-calculus definition and switching the word
lambda for fn, gives us this incomprehensible mess!
(defn Y [r]
((fn [f] (f f))
(fn [f]
(r (fn [x] ((f f) x))))))
But what does it actually mean? Probably the best way to understand is with a real example and to do that, we need a recursive function. Given that everyone else uses factorial, we'll use a simpler recursive function that sums up a sequence.
(defn sum-seq [x]
(if (empty? x)
0
(+ (first x) (sum-seq (rest x)))))
In the definition above, we've written the function with explicit recursion. We'll use the Y combinator to get rid of that!
The first step is to rethink the function in terms of a series of functions. Our goal is to create a way of expressing this computation as a series of function calls. We want to write a function that given a function to compute the sum of a sequence, gives us the next function to compute the sum of a sequence.
(defn sum-seq-fn-gen [func]
(fn [s]
(if (empty? s)
0
(+ (first s) (func (rest s))))))
So now we have such a function. We can already use it:
user> ((sum-seq-fn-gen nil) [])
0
user> ((sum-seq-fn-gen (sum-seq-fn-generator nil)) [9])
9
user> ((sum-seq-fn-gen (sum-seq-fn-gen (sum-seq-fn-gen nil))) [1 9])
10
It's not that useful, as at the moment we'd have to type in an awful lot of characters to sum a large list. What we really want is some way of calculating the fixed point of such a function. Thankfully we already have that, thanks to the Y combinator.
user> ((Y sum-seq-fn-gen) [1 2 3 4 5])
15
user> ((Y sum-seq-fn-gen) (range 0 1000))
499500
So the Y Combinator has given us what we need. Given a function and an input, find the fixed point. Note that there is no explicit recursion going on.
sum-seq-fn-gen could be an anonymous function.
user> ((Y
(fn [func]
(fn [s]
(if (empty? s)
0
(+ (first s) (func (rest s))))))) [1 2 3 4 5])
15
The best way to understand the Y combinator is to see how it's used and then run through the fun exercise of expanding it and seeing what happens. I found the links below useful:
Labels: clojure
# posted by Jeff Foster : 23:04
Subscribe to Posts [Atom]
