On Wed, May 9, 2012 at 1:00 PM, Rich Hickey <
richh...@gmail.com> wrote:
> This analogy is not quite right.
>
>> (fn [n] (vector n (+ n 1))
>
> is not a reducing fn. Tt is a cons cell builder, and the Church encoding builds lists.
>
It is because I did not write it in the right way. Sorry about that.
It can be made nicer with protocols, probably. But the idea is quite simple.
Something is generative (dual to reducible) if it contains a seed, a
function from seed to the first element (called now)
and a function from a seed to the next seed (called later).
Then
(defn from [n]
[n id inc])
(def nat (from 0))
Then, take converts a generative to a reducible:
(defn take [n [seed now later]]
(fn [ r ] ; r is the function we reduce with
(loop [m (long n) seed seed acc (r) ]
(if (zero? m) acc
(recur (dec m) (later seed) (r acc (now seed)))
) )
So in (reduce + (map square (take n nat))), there is no cell cons
created in any way.
It just beta-reduces to the loop someone would write for the same problem:
(without any kind of deforestation):
(loop [m (long n) seed 0 acc 0 ]
(if (zero? m) acc
(recur (dec m) (inc seed) (+ acc (square seed)))
By the way, map has also a definition in the generative setting:
(defn map-generative [f [seed now later] ]
[seed (comp now f) later])
There might be multiple interesting way to convert from generative to reducible.
take is one, until can be another:
(defn until [p [seed now later]]
(fn [ r ]
(loop [seed seed acc (r) ]
(let [v (now seed)]
(if (p v)
acc
(recur (later seed) (r acc v)))))))
It can happen than this never ends if p is never true. (You can add an
optional limit on the number of elements.)
Then to sum all squared number smaller than 1000000:
(reduce + (until #(% > 1000000) (map square nat))
Then again, no cons cell allocated.
It is straightforward to extend the generative things so that they can
finish early, when now returns nil
for example. Then you can convert easily those finite generative to reducible.
One last point: you can convert any sequence (including infinite
streams) to a generative by using
(fn [s] [ s first next ] )
It is also possible to convert any generative to a stream (for
memoisation for example)
However,the generative representation is independent of the sequence
representation.
> It is only by doing this that you can get the true prize of this library - versions of map/filter etc that can be run in parallel, and that are completely independent of the data structures on which they are run.
>
It is less clear that generative things are amenable to //-reduction.
However, it should be possible to add a function to jump ahead.( [seed
now later jump] )
This function could default to calling later repeatedly, but can
sometimes be implemented more efficiently.
It might be possible to do better if your reduction function is commutative.
I am not saying it replaces reducible, but that it can be an
interesting complement for a generate/reduce pattern.
I hope it clarifies my last email.
Best,
Nicolas.