reduction

16 views
Skip to first unread message

Chouser

unread,
Dec 5, 2008, 10:50:10 AM12/5/08
to clo...@googlegroups.com
Google groups files section is having issues.
Here's 'reduction' as discussed in IRC, mostly written by Rich.

--Chouser

reduction.patch

Rich Hickey

unread,
Dec 5, 2008, 11:00:11 AM12/5/08
to Clojure


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.
>

Attachments are preferred - thanks!

Rich

Randall R Schulz

unread,
Dec 5, 2008, 11:08:29 AM12/5/08
to clo...@googlegroups.com

It came through as an attachment here.


> Rich


Randall Schulz

Chouser

unread,
Dec 5, 2008, 11:34:59 AM12/5/08
to clo...@googlegroups.com
On Fri, Dec 5, 2008 at 10:50 AM, Chouser <cho...@gmail.com> wrote:
> 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

reduction.patch

Chouser

unread,
Dec 5, 2008, 9:55:37 PM12/5/08
to clo...@googlegroups.com
Third time's charm? The previous versions of 'reduction' returned nil
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

reduction.patch

Chouser

unread,
Dec 6, 2008, 1:00:20 AM12/6/08
to clo...@googlegroups.com
On Fri, Dec 5, 2008 at 9:55 PM, Chouser <cho...@gmail.com> wrote:
> 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

unread,
Dec 6, 2008, 2:12:31 AM12/6/08
to clo...@googlegroups.com
How about this one? Same results as in my previous post. Still as
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

unread,
Dec 6, 2008, 4:27:02 AM12/6/08
to clo...@googlegroups.com
Chouser a écrit :
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.

Christophe

Chouser

unread,
Dec 6, 2008, 8:41:05 AM12/6/08
to clo...@googlegroups.com
On Sat, Dec 6, 2008 at 4:27 AM, Christophe Grand <chris...@cgrand.net> wrote:
>
> 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

unread,
Dec 7, 2008, 5:29:25 AM12/7/08
to clo...@googlegroups.com
Chouser a écrit :

> 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?
>
The problem is that to compute the rest (reduction f init coll) you call
(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

unread,
Dec 7, 2008, 7:41:29 AM12/7/08
to Clojure
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:

(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) (delay (rest coll)))
(list (f))))
([f init coll]
(lazy-cons init
(let [s (seq (force coll))]
(and s (reduction f (f init (first s))
(delay (rest s))))))))

Rich

Christophe Grand

unread,
Dec 7, 2008, 4:10:02 PM12/7/08
to clo...@googlegroups.com
Rich Hickey a écrit :

> 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
Thanks Rich! I wasn't aware that (force x) returns x if x is not a
Delay, this is good to know. (I assume that having seq to automatically
force its argument would be a perf killer.)

Rich Hickey

unread,
Dec 8, 2008, 8:59:24 AM12/8/08
to Clojure
It's less the perf than that it is a different model, e.g. (delay nil)
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

unread,
Dec 12, 2008, 3:35:03 PM12/12/08
to clo...@googlegroups.com
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].

Christophe

Chouser a écrit :

Rich Hickey

unread,
Dec 15, 2008, 7:59:20 AM12/15/08
to Clojure


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].
>

Very clever.

Rich

Chouser

unread,
Jan 2, 2009, 10:29:23 AM1/2/09
to Clojure
On Dec 12 2008, 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))))

This isn't in clojure.core yet (any reason why not?) so would you mind
if I add it to clojure.contrib.seq-utils? Or of course you can do it
if you prefer. :-)

--Chouser

Christophe Grand

unread,
Jan 5, 2009, 9:53:52 AM1/5/09
to clo...@googlegroups.com
Chouser a écrit :

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

unread,
Jan 5, 2009, 10:35:15 AM1/5/09
to clo...@googlegroups.com

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

unread,
Jan 5, 2009, 11:00:43 AM1/5/09
to clo...@googlegroups.com
Chouser a écrit :

>> 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.
>
I never liked my iterate-based function: it is overly complicated (I
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

unread,
Jan 5, 2009, 11:37:24 AM1/5/09
to clo...@googlegroups.com, the.stua...@gmail.com
Chouser a écrit :

> On Mon, Jan 5, 2009 at 9:53 AM, Christophe Grand <chris...@cgrand.net> wrote:
>
>> Chouser a écrit :
>>
>>> This isn't in clojure.core yet (any reason why not?) so would you mind
>>> if I add it to clojure.contrib.seq-utils? Or of course you can do it
>>> if you prefer. :-)
>> hat 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.
Stuart,

Do you think rec-cat, rec-cons and reductions belong to seq-utils?

Christophe

Stuart Sierra

unread,
Jan 5, 2009, 7:11:05 PM1/5/09
to Christophe Grand, clo...@googlegroups.com
On Mon, Jan 5, 2009 at 11:37 AM, Christophe Grand <chris...@cgrand.net> wrote:
> 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

Reply all
Reply to author
Forward
0 new messages