a better reductions?

[Stuart Halloway]

Is the following an improvement on clojure.contrib.seq-utils/
reductions, or a step backwards?

(defn my-reductions
([f coll]
(if (seq coll)
(cons (first coll) (my-reductions f (first coll) (rest coll)))
(cons (f) nil)))
([f acc coll]
(if (seq coll)
(let [nextval (f acc (first coll))]
(lazy-seq (cons nextval (my-reductions f nextval (rest
coll))))))))

On the plus side, it appears to be faster (as collections grow large),
and it doesn't "cheat" by introducing an atom. On the minus side it
isn't as pretty as the one in contrib.

Stu

[Sean Devlin]

It seems to have the same signature, so as a consumer of the library
it's the same to me. If the speedup holds, I say make the change to
your version.

The only warning is that I couldn't find any regression tests for seq-
utils. Perhaps this is a chance to add some.

My $.02

Sean

[Sean Devlin]

One more thought. I'd change the signature of the second call to

[f init coll]

This matches the original reductions.

[Lauri Pesonen]

Hi Stuart,

2009/8/6 Stuart Halloway <stuart....@gmail.com>:

>
> On the plus side, it appears to be faster (as collections grow large),
> and it doesn't "cheat" by introducing an atom. On the minus side it
> isn't as pretty as the one in contrib.

While maybe not as pretty as the one in contrib, it's not a monster
either. Shouldn't we aim for efficiency rather than elegance in
library routines (within reason)? I think the user will appreciate the
speedy version more than the pretty version. Since this change retains
the original interface, I would say go for it.

I'm a bit confused by the (cons (f) nil) form in the else clause. It
is going to fail unless f is of 0 arity. If f is of arity 2 we get an
IllegalArgumentException from eval. So wouldn't it be more correct to
return an empty list?

> Stu

--
! Lauri

[Daniel Lyons]

On Aug 7, 2009, at 2:59 AM, Lauri Pesonen wrote:
> While maybe not as pretty as the one in contrib, it's not a monster
> either. Shouldn't we aim for efficiency rather than elegance in
> library routines (within reason)? I think the user will appreciate the
> speedy version more than the pretty version. Since this change retains
> the original interface, I would say go for it.

This is the difference between FreeBSD and NetBSD. I agree, but I also
find it useful to crack open core and contrib to see coding examples
and to understand algorithms. It's a balancing act. I'm definitely for
this change though. I use reductions from time to time.

—
Daniel Lyons

[Rich Hickey]

Good call, the version in contrib predates lazy-seq and full laziness.
You can see the challenges faced in its implementation (back in the
lazy-cons days) here:

http://groups.google.com/group/clojure/browse_thread/thread/3edf6e82617e18e0/58d9e319ad92aa5f?#58d9e319ad92aa5f

But, the version you have isn't fully lazy either. As a general rule,
lazy-seq should wrap the entire body:

(defn reductions
([f coll]
(lazy-seq
(if (seq coll)
(cons (first coll) (reductions f (first coll) (rest coll)))
(cons (f) nil))))
([f acc coll]
(lazy-seq

(if (seq coll)
(let [nextval (f acc (first coll))]

(cons nextval (reductions f nextval (rest coll))))))))

Rich

[Sean Devlin]

I have to revise my last recommendation. The signature of the second
call should be

[f val coll]

in order to match reduce. Admittedly, this is a tiny detail.

Sean

[Mark Engelberg]

I believe that if you're going for speed, another trick is to use
if-let to bind a name to (seq coll) and reuse the new name, rather
than coll, when applying first and rest later in the function.

[Vagif Verdi]

On Aug 7, 1:23 am, Daniel Lyons <fus...@storytotell.org> wrote:
> This is the difference between FreeBSD and NetBSD. I agree, but I also  
> find it useful to crack open core and contrib to see coding examples  
> and to understand algorithms.

I'd suggest to include into library for teaching purposes variants of
unoptimized functions with a suffix -naive. Say reduction-naive.
This way you could have both beautiful algorithm for teaching
purposes, and optimized function for practical purposes.

[Daniel Werner]

On Aug 7, 8:40 pm, Vagif Verdi <Vagif.Ve...@gmail.com> wrote:
> I'd suggest to include into library for teaching purposes variants of
> unoptimized functions with a suffix -naive. Say reduction-naive.
> This way you could have both beautiful algorithm for teaching
> purposes, and optimized function for practical purposes.

Alternatively, these variants could be included in a commented-out
form. Thus they won't get compiled and loaded, but still be a help to
the curious programmer browsing the Clojure sources.