reduction
Rich Hickey
On Dec 5, 10:50 am, Chouser <chou...@gmail.com> wrote:
> Google groups files section is having issues.
> Here's 'reduction' as discussed in IRC, mostly written by Rich.
>
Rich
Randall R Schulz
It came through as an attachment here.
> Rich
Randall Schulz
Chouser
> Google groups files section is having issues.
> Here's 'reduction' as discussed in IRC, mostly written by Rich.
I messed it up anyway -- tried to use if-let too early.
Try this patch instead.
--Chouser
Chouser
for empty collection when no init was given. This version follows
'reduce' more closely, calling the given function with no arguments:
user=> (reduction + [])
(0)
--Chouser
Chouser
> Third time's charm?
Apparently not. Previous versions had a couple problems.
One was that when when no init was provided, the first element of the
collection was not emitted by itself. This is inconsistent with
Haskell's scanl1 and I think also inconsistent with itself.
Another issue is that they looked ahead in the collection one step
further than required to produce each value. This type of issue has
caused me problems in the past when working with lazy sequences whose
cost rose sharply with each successive 'rest'.
But I found it tricky to fully solving this last problem. Here is
a definition that almost completely solves the problem:
(defn reduction
"Returns a lazy seq of the intermediate values of the reduction (as
per reduce) of coll by f, starting with init."
([f coll]
(if (seq coll)
(reduction f (first coll) (rest coll))
(cons (f) nil)))
([f init coll]
(let [step (fn step [prev coll]
(when (seq coll)
(let [x (f prev (first coll))]
(lazy-cons x (step x (rest coll))))))]
(lazy-cons init (step init coll)))))
That one still consumes one extra value for the first value it
produces when called with no init. The second value is then produced
without it calling 'rest' again, and so the producer is caught up with
the consumer for the rest of the seq.
There are a few ways to solve this small early eagerness, and below is
my best attempt. Whether it's worth the extra (private) function for
this narrow case is a question I leave to others. Both definitions of
'reduction' produce the same results in all cases, the only difference
is in how early the first 'rest' is called on the collection.
(defn- reduction-step [f prev coll]
(when (seq coll)
(let [x (f prev (first coll))]
(lazy-cons x (reduction-step f x (rest coll))))))
(defn reduction
"Returns a lazy seq of the intermediate values of the reduction (as
per reduce) of coll by f, starting with init."
([f coll]
(if (seq coll)
(lazy-cons (first coll) (reduction-step f (first coll) (rest coll)))
(cons (f) nil)))
([f init coll]
(lazy-cons init (reduction-step f init coll))))
Either solution can be made available in patch form upon request.
--Chouser
Chouser
lazy as possible. Plus it's so cute!
(defn reduction
"Returns a lazy seq of the intermediate values of the reduction (as
per reduce) of coll by f, starting with init."
([f coll]
(if (seq coll)
(lazy-cons (first coll) (map f (reduction f coll) (rest coll)))
(cons (f) nil)))
([f init coll]
(lazy-cons init (map f (reduction f init coll) coll))))
--Chouser
Christophe Grand
recursively such lists but the only way I found involves using mutation.
Now with an atom it must be cleaner.
Christophe
Chouser
>
> But I don't think it's still O(n). I searched for a way to define
> recursively such lists but the only way I found involves using mutation.
> Now with an atom it must be cleaner.
Your comprehension of such things is clearly deeper than mine.
Testing just now on large collections, the version using 'map' is
indeed not only slower, but also overflows the stack. Hm... and
perhaps I see why now. Is it computing the entire chain up to each
result -- O(n^2), demanding n stack frames for the nth result?
Anyway, either of the definitions presented together work fine for
large collections and appear to operate in O(n) as you'd expect.
--Chouser
Christophe Grand
> Testing just now on large collections, the version using 'map' is
> indeed not only slower, but also overflows the stack. Hm... and
> perhaps I see why now. Is it computing the entire chain up to each
> result -- O(n^2), demanding n stack frames for the nth result?
>
(reduction f init coll) again. So, as you said, at each step you are
computing the entire chain up to each result.
The expansion of you code (by replacing (reduction f init coll) by its
definition) is:
(lazy-cons init (map f (rest coll)
(lazy-cons init (map f (rest coll)
(lazy-cons init (map f (rest coll)
(lazy-cons init (map f (rest coll)
(...))))
And here is what I mean by "using mutation" to solve this problem (it's
a kind of memoization):
(defn reduction
"Returns a lazy seq of the intermediate values of the reduction (as
per reduce) of coll by f, starting with init."
([f coll]
(if (seq coll)
(reduction f (first coll) (rest coll))
(cons (f) nil)))
([f init coll]
(let [self (atom nil)
result (lazy-cons init (map f @self coll))]
(swap! self (constantly result))
result)))
Christophe
Rich Hickey
work was being done in the current case that needn't be (checking the
status of coll), and that we need more laziness than lazy-cons gives
us (we need to delay evaluation of one argument to the recursive
call). delay/force offer laziness a la carte:
(defn reduction
"Returns a lazy seq of the intermediate values of the reduction (as
per reduce) of coll by f, starting with init."
([f coll]
(if (seq coll)
(list (f))))
(lazy-cons init
(and s (reduction f (f init (first s))
(delay (rest s))))))))
Rich
Christophe Grand
> I think the problem is that in the original and subsequent versions,
> work was being done in the current case that needn't be (checking the
> status of coll), and that we need more laziness than lazy-cons gives
> us (we need to delay evaluation of one argument to the recursive
> call). delay/force offer laziness a la carte
Delay, this is good to know. (I assume that having seq to automatically
force its argument would be a perf killer.)
Rich Hickey
is logical true. Using delays internally is one thing, but were they
to leak out, it would break the seq/no-seq(nil) model, and instead
require all use of seqs to force or be wrapped in macros that do the
forcing. I'm not saying that's wrong, but I thought it would be more
cumbersome than the current model which abstracts CL's cons cells.
In practice, we've ended up with more calls to seq than I envisioned,
mostly to allow fns to work with anything seq-able, so must seq on
entry, but there are still plenty of places where it is convenient not
to have to call seq, and directly test the sequence in conditionals,
and few where not having seqs be universally (potentially) delayed is
a hindrance.
Rich
Christophe Grand
(defn reductions
"Returns a lazy seq of the intermediate values of the reduction (as
per reduce) of coll by f, starting with init."
([f coll]
(if (seq coll)
(for [s (iterate (fn [[x & s]] (if s
(lazy-cons (f x (first s)) (rest s))))
coll)
:while s]
(first s))
(list (f))))
([f val coll]
(reductions f (cons val coll))))
It's interesting that the general case is [f coll] and not [f val coll].
Christophe
Chouser a écrit :
Rich Hickey
On Dec 12, 3:35 pm, Christophe Grand <christo...@cgrand.net> wrote:
> I was sure it was a job for iterate:
>
> (defn reductions
> "Returns a lazy seq of the intermediate values of the reduction (as
> per reduce) of coll by f, starting with init."
> ([f coll]
> (if (seq coll)
> (for [s (iterate (fn [[x & s]] (if s
> (lazy-cons (f x (first s)) (rest s))))
> coll)
> :while s]
> (first s))
> (list (f))))
> ([f val coll]
> (reductions f (cons val coll))))
>
> It's interesting that the general case is [f coll] and not [f val coll].
>
Rich
Chouser
wrote:
>
> (defn reductions
> "Returns a lazy seq of the intermediate values of the reduction (as
> per reduce) of coll by f, starting with init."
> ([f coll]
> (if (seq coll)
> (for [s (iterate (fn [[x & s]] (if s
> (lazy-cons (f x (first s)) (rest s))))
> coll)
> :while s]
> (first s))
> (list (f))))
> ([f val coll]
> (reductions f (cons val coll))))
if I add it to clojure.contrib.seq-utils? Or of course you can do it
if you prefer. :-)
--Chouser
Christophe Grand
What do you think of adding rec-cons, rec-cat and your (fixed) cute
version instead to seq-utils?
(see http://clj-me.blogspot.com/2009/01/recursive-seqs.html for rec-cat
and rec-cons)
Chouser
That'd be fine too, especially for rec-cons and rec-cat. The
'reduction' in your blog makes a nice example, but I assume it runs
slower than your version above.
--Chouser
Christophe Grand
>> What do you think of adding rec-cons, rec-cat and your (fixed) cute
>> version instead to seq-utils?
>> (see http://clj-me.blogspot.com/2009/01/recursive-seqs.html for rec-cat
>> and rec-cons)
>>
>
> That'd be fine too, especially for rec-cons and rec-cat. The
> 'reduction' in your blog makes a nice example, but I assume it runs
> slower than your version above.
>
wrote it because the intuition that iterate can be used kept nagging me)
and yours (built with rec-cons) is more than twice faster!
Christophe
Christophe Grand
> On Mon, Jan 5, 2009 at 9:53 AM, Christophe Grand <chris...@cgrand.net> wrote:
>
>> Chouser a écrit :
>>
>>> if I add it to clojure.contrib.seq-utils? Or of course you can do it
>>> if you prefer. :-)
>> version instead to seq-utils?
>> (see http://clj-me.blogspot.com/2009/01/recursive-seqs.html for rec-cat
>> and rec-cons)
>>
>
> That'd be fine too, especially for rec-cons and rec-cat.
Do you think rec-cat, rec-cons and reductions belong to seq-utils?
Christophe
Stuart Sierra
> Stuart,
>
> Do you think rec-cat, rec-cons and reductions belong to seq-utils?
>
> Christophe
>
Find by me. I won't claim ownership over seq-utils or str-utils. As
far as I'm concerned, any contrib committers can add to them.
-Stuart Sierra