Just last week I finally got my "Advanced Practical Recursion in Lisp
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
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
