Advanced Practical Recursion in Lisp 1.0
David Sletten
1.0" kit from Y-Combinator Technologies, Inc. (not Paul Graham's
company). They have this amazing product that I think we can use in
Clojure. I'm not supposed to share the source code, but I can trust
you folks right?
The main component is this function Y:
(defn Y [m]
((fn [future]
(m (fn [arg]
((future future) arg))))
(fn [future]
(m (fn [arg]
((future future) arg)))) ))
You can use this to define anonymous recursive functions.
"Why would I want to do that?", you ask yourself. Well, let me tell
you why. Ordinarily we would define a recursive function like this:
(defn factorial [n]
(if (zero? n)
1
(* n (factorial (dec n)))) )
The function body naturally contains a reference to
itself--'factorial'-- in order to compute the recursive cases.
But what if we wanted to apply an anonymous recursive function
directly to an argument:
((fn [n] (if (zero? n) 1 (* n (?? (dec n))))) 6)
What do we put where the ?? is? This function has no name, so how can
it call itself?
That's where "Advanced Practical Recursion in Lisp 1.0" (APRiL 1.0)
comes in! Using the function Y above, the problem disappears:
((Y (fn [rec]
(fn [n]
(if (zero? n)
1
(* n (rec (dec n)))) ))) 6)
=> 720
What could be simpler than that?
Here are a few more familiar examples.
Fibonacci numbers? No problem:
((Y (fn [rec]
(fn [n]
(cond (= n 0) 0
(= n 1) 1
:else (+ (rec (- n 1)) (rec (- n 2)))) ))) 10)
=> 55
Find the length of a list:
((Y (fn [rec]
(fn [l]
(if (empty? l)
0
(inc (rec (rest l)))) ))) '(a b c d e))
=> 5
How about reversing a list? This one's really recursive (quadruply)!
((Y (fn [rec]
(fn [l]
(cond (empty? l) '()
(empty? (rest l)) (list (first l))
:else (cons (first (rec (rest l)))
(rec (cons (first l)
(rec (rest (rec (rest
l)))) )))) )))
'(a b c d e))
=> (e d c b a)
There's even an experimental version of Y that can handle anonymous
functions with multiple parameters:
(defn Y2 [m]
((fn [future]
(m (fn [& args]
(apply (future future) args))))
(fn [future]
(m (fn [& args]
(apply (future future) args)))) ))
Using this we can remove elements that we don't want from a list:
((Y2 (fn [rec]
(fn [obj l]
(cond (empty? l) '()
(= (first l) obj) (rec obj (rest l))
:else (cons (first l) (rec obj (rest l)))) )))
'pung
'(pung foo bar baz pung baz bar pung foo))
=> (foo bar baz baz bar foo)
Replace certain elements in a list:
((Y2 (fn [rec]
(fn [new old l]
(cond (empty? l) '()
(= (first l) old) (cons new (rec new old (rest l)))
:else (cons (first l) (rec new old (rest l)))) )))
'pung
'foo
'(pung foo bar baz pung bar foo))
=> (pung pung bar baz pung bar pung)
Or in an arbitrary tree:
((Y2 (fn [rec]
(fn [new old obj]
(cond (= obj old) new
(and (coll? obj) (seq obj)) (cons (rec new old (first
obj))
(rec new old (rest
obj)))
:else obj))))
'a
'b
'(a ((b) c (a b c)) d (a b)))
=> (a ((a) c (a a c)) d (a a))
Now here's the exciting part. I'm trying to work out some sort of
licensing deal for us. If the price is right we can use APRiL 1.0 to
streamline Clojure code. For instance, we won't need 'map' anymore:
((Y2 (fn [rec]
(fn [f l]
(if (empty? l)
'()
(cons (f (first l)) (rec f (rest l)))) )))
inc
(range 10))
=> (1 2 3 4 5 6 7 8 9 10)
((Y2 (fn [rec]
(fn [f l]
(if (empty? l)
'()
(cons (f (first l)) (rec f (rest l)))) )))
#(.toUpperCase %)
'("Is" "this" "not" "pung?"))
=> ("IS" "THIS" "NOT" "PUNG?")
But wait, there's more!! We won't need 'reduce' either:
((Y2 (fn [rec]
(fn [f start l]
(if (empty? l)
start
(f (first l) (rec f start (rest l)))) )))
+
0
[1 2 3 4 5])
=> 15
((Y2 (fn [rec]
(fn [f start l]
(if (empty? l)
start
(f (first l) (rec f start (rest l)))) )))
*
1
[1 2 3 4 5 6])
=> 720
I hope that you can start to see the potential here! There are no
doubt many other superfluous operators just clogging up Clojure that
you'd rather live without (No offense, Rich. I'm sure you tried your
best. :-) ). I'm eager to hear your suggestions!!
I'm optimistic that the company is willing to work with us, but if
their price is too high they do have another cheaper option. There is
a reduced rate anonymous Y function as well. Even Y doesn't need a
name--we just use it directly. Cut out the middleman and everyone wins!
Here's 'length' again:
(((fn [m]
((fn [future]
(m (fn [arg]
((future future) arg))))
(fn [future]
(m (fn [arg]
((future future) arg)))) ))
(fn [rec]
(fn [l]
(if (empty? l)
0
(inc (rec (rest l)))) )))
'(a b c d e))
=> 5
And 'reverse':
(((fn [m]
((fn [future]
(m (fn [arg]
((future future) arg))))
(fn [future]
(m (fn [arg]
((future future) arg)))) ))
(fn [rec]
(fn [l]
(cond (empty? l) '()
(empty? (rest l)) (list (first l))
:else (cons (first (rec (rest l)))
(rec (cons (first l)
(rec (rest (rec (rest l)))) )))) )))
'(a b c d e))
=> (e d c b a)
Breathtaking in its elegance!
I'm going to move forward with the negotiations, but I need to know
if you, the Clojure community, are on board here. Ultimately the
decision is going to come down to whether or not you find the APRiL
1.0 technology useful. Try it out and let me know your opinions.
Aloha,
David Sletten
Paul Stadig
Indeed! :)
I'm going to move forward with the negotiations, but I need to know
if you, the Clojure community, are on board here. Ultimately the
decision is going to come down to whether or not you find the APRiL
1.0 technology useful. Try it out and let me know your opinions.
I think I'll wait for APRiL 2.0. I often find that when I jump right into version 1.0 of a product, I'm made a fool!
Aloha,
David Sletten
Paul
Remco van 't Veer
> [snip]
> I'm going to move forward with the negotiations, but I need to know
> if you, the Clojure community, are on board here. Ultimately the
> decision is going to come down to whether or not you find the APRiL
> 1.0 technology useful. Try it out and let me know your opinions.
This technology is too cool to be true! I'll chip in and donate all
my spare parens (thanks Rich)!
Remco
revoltingdevelopment
case).