Processing list more elegantly

[Conrad]

I've been writing Clojure code today and have noticed the same pattern
show up multiple times, but can't find an elegant way to code it in
idiomatic Clojure. I feel like I'm missing an obvious solution...
anyone else see something I don't? Thanks in advance!

The problem boils down to the following minimal example: Suppose you
want to write a function "left-total" which takes a list of number and
returns pairs of said numbers, along with the total of numbers to the
left:

=> (left-total [3 5 10 1 2 7])
([3 0] [5 3] [10 8] [1 18] [2 19] [7 21])

I can think of several ways to write this function. Three acceptable
versions of this function are written below, but all of them are
hideous looking. Is there a better solution? (Note that any solution
should avoid thrashing the stack or performing more than the minimum
number of additions.)

(defn left-total [lst]
(loop [lst lst
acc nil
tot 0]
(if (seq lst)
(let [[cur & more] lst]
(recur more (cons [cur tot] acc) (+ tot cur)))
(reverse acc))))

(defn left-total [lst]
(reverse (first (reduce (fn [[acc tot] cur]
[(cons [cur tot] acc) (+ tot cur)])
[nil 0]
lst))))

(defn left-total [lst]
(let [tot (atom 0)]
(map (fn [cur]
(let [old-tot @tot]
(swap! tot (partial + cur))
[cur old-tot]))
lst)))

[David Cabana]

Try this:

(use '[clojure.contrib.seq-utils :only (reductions)])

(defn left-total [lst]
(map vector lst
(reductions + (cons 0 lst))))

[Conrad]

Thanks David... that indeed looks like the solution I was looking for
(unless of course there's an elegant way to do it with clojure.core,
too :-)

...you could simplify it even more by doing the following:

(defn left-total [lst]
(map vector lst

(reductions + 0 lst)))

[Conrad]

...for some reason, however, this version is a lot slower than my 3
versions of the code- Not sure if it's the laziness of this version,
or if there's stuff being put on the call stack by "reductions"...

The following code executes in less than 2 seconds for any of my
versions of the function on my box, but it takes over 4 seconds for
the version using "reductions":

(time (do (doall (left-total (range 1000000))) nil))

On Dec 27, 8:52 pm, David Cabana <drcab...@gmail.com> wrote:

[David Cabana]

If speed matters, I found both of these to be faster than the version
using reductions.

First version is to roll my own replacement for reductions,
specialized to addition:

(defn partial-sums [coll]
(loop [result [0]
tot 0
terms coll]
(if (empty? terms)
result
(let [next (+ tot (first terms))]
(recur (conj result next)
next
(rest terms))))))

(defn left-tot1 [lst]
(map vector lst
(partial-sums lst)))

Even faster is this one, which is something along the lines of one of
you original versions,
but without a list reversal.

(defn left-tot2 [lst]
(loop [result [ ]
tot 0
terms lst]

(if (empty? terms)
result
(let [f (first terms)]
(recur (conj result [f tot])
(+ tot f)
(rest terms))))))

[Fogus]

How about this?

(defn left-total [coll]
(map (fn [[l r]] [l (reduce + r)])
(for [i (range (count coll))]
[(first (drop i coll)) (take i coll)])))

-m

[Conrad]

Hmmm... I didn't think of using cons/vectors to avoid the reverse...

[Conrad]

That one is elegant, but uses more than the minimum number of
additions, one of the conditions I mentioned in the original post. (In
real instances of this pattern in my code, the addition contains other
function that are very costly to perform, which is part of the reason
for this post.)

[Conrad]

"conj", I mean.

[Fogus]

> That one is elegant, but uses more than the minimum number of
> additions, one of the conditions I mentioned in the original post. (In

Ah yes... *now* I see that requirement. Well, thanks for the
interesting exercise in any case. :-)

-m

[Conrad]

I think this is indeed the best way to do this- On closer examination,
although there's some overhead in using "reductions" it appears to be
slower by only a constant factor- So with larger data sets it'll
retain a reasonable performance, same ball park as my tail-call
optimized versions.

[Meikel Brandmeyer]

Hi,

Am 28.12.2009 um 02:36 schrieb Conrad:

> => (left-total [3 5 10 1 2 7])
> ([3 0] [5 3] [10 8] [1 18] [2 19] [7 21])

If in doubt, use lazy-seq.

(defn left-total
[accum-fn accum s]
(lazy-seq
(when-let [[f & r] (seq s)]
(cons [f accum] (left-total accum-fn (accum-fn accum f) r)))))

user=> (left-total + 0 [3 5 10 1 2 7])

([3 0] [5 3] [10 8] [1 18] [2 19] [7 21])

Since you said, that + is more complicated in your specific case, you might want this more general form. Otherwise the above can of course be simplified…

Sincerely
Meikel

[Conrad]

Thanks Meikel- Let me see if I understand what's going on here...

Usually, calling "left-total" recursively from a non-tail call
position, as you do in this example, would abuse the call stack.
However, since the call is happening from within a lazy-seq, does this
mean the number of items on the call stack will remain unhindered,
despite the non-tail-call recursion?

Experimentally, this version seems to perform as well as any of my
solutions (under 2 secs for 1 mil items) This suggests it is, indeed,
not causing any abuse of the call stack.

This is definitely cleaner and more flexible than any other solution
suggested so far, I think.

[Timothy Pratley]

I find this quite interesting because Meikel has effectively created a
faster version of reductions:

(defn cumulative
([accum-fn s]
(rest (cumulative accum-fn 0 s)))
([accum-fn accum s]

(lazy-seq
(when-let [[f & r] (seq s)]

(cons accum (cumulative accum-fn (accum-fn accum f) r))))))

(defn left-total
[coll]
(map list coll (cumulative + 0 coll)))

I did some microbenchmarking and it does appear to be 2x as fast as
reductions, and processes the special case left-total just as fast as
one of the original proposals. Oddly left-tot2 performs very poorly
though it was claimed to be fast. I suppose this could be yet another
case of microbenchmarking being evil - but looking at the code the
reductions version seems to use an atom which implies some unnecessary
overhead? Or maybe I am missing something important about their
differences.

I followed the link to the discussion about the original reductions
and it all seems to be pre-lazy-seq so maybe this is just a case of
the function should be updated?

Below are the timing results (don't recommend basing anything off them
as just adhoc)

user=> (time (dotimes [i 10000000] (left-total3 coll)))
"Elapsed time: 1460.309131 msecs"
nil
user=> (time (dotimes [i 10000000] (left-total3 coll)))
"Elapsed time: 1600.225655 msecs"
nil
user=> (time (dotimes [i 10000000] (left-total2 coll)))
"Elapsed time: 960.000014 msecs"
nil
user=> (time (dotimes [i 10000000] (left-total2 coll)))
"Elapsed time: 957.096643 msecs"
nil
user=> (time (dotimes [i 10000000] (left-total coll)))
"Elapsed time: 702.240509 msecs"
nil
user=> (time (dotimes [i 10000000] (left-total coll)))
"Elapsed time: 685.018973 msecs"
nil
user=> (time (dotimes [i 10000000] (left-total3 coll)))
"Elapsed time: 1492.383251 msecs"
nil
user=> (time (dotimes [i 10000000] (left-total coll)))
"Elapsed time: 719.915803 msecs"
nil
user=> (time (dotimes [i 10000000] (left-tot2 coll)))
"Elapsed time: 10286.935494 msecs"

(defn left-total2 [lst]

(let [tot (atom 0)]
(map (fn [cur]
(let [old-tot @tot]
(swap! tot (partial + cur))
[cur old-tot]))
lst)))

(use 'clojure.contrib.seq-utils)
(defn left-total3
[coll]
(map list coll (reductions + 0 coll)))

(defn left-tot2 [lst]
(loop [result [ ]
tot 0
terms lst]

(if (empty? terms)
result
(let [f (first terms)]
(recur (conj result [f tot])
(+ tot f)
(rest terms))))))

2009/12/29 Conrad <drc...@gmail.com>:

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

[Conrad]

I think you're right on the money here, Timothy: I'm not a Clojure
guru, but it does seem from a naive perspective that Meikel's code
let's you implement "reductions" in a way that significantly
outperforms the current implementation.

[Oleg Vershinin]

On 28 дек, 05:36, Conrad <drc...@gmail.com> wrote:
> I've been writing Clojure code today and have noticed the same pattern
> show up multiple times, but can't find an elegant way to code it in
> idiomatic Clojure. I feel like I'm missing an obvious solution...
> anyone else see something I don't? Thanks in advance!
>
> The problem boils down to the following minimal example: Suppose you
> want to write a function "left-total" which takes a list of number and
> returns pairs of said numbers, along with the total of numbers to the
> left:
>
> => (left-total [3 5 10 1 2 7])
> ([3 0] [5 3] [10 8] [1 18] [2 19] [7 21])
>

what about:

(defn left-total [s]
(reverse (reduce (fn [y x] (cons (list x (reduce + (first y))) y))
() s)))

user> (left-total [3 5 10 1 2 7])
((3 0) (5 3) (10 8) (1 18) (2 19) (7 21))

[Oleg Vershinin]

>
> (defn left-total [lst]
>   (reverse (first (reduce (fn [[acc tot] cur]
>                             [(cons [cur tot] acc) (+ tot cur)])
>                           [nil 0]
>                           lst))))

(defn left-total [s]

(reverse (reduce (fn [y x] (cons (list x (reduce + (first y))) y))
() s)))

sorry, had not read whole message

[Rich Hickey]

This was discussed before, the new version never made it into a patch:

http://groups.google.com/group/clojure/msg/43de40f078a291cc

Note your use of destructuring in when-let with & makes your
cumulative slightly non-lazy.

Rich

[Timothy Pratley]

2009/12/30 Rich Hickey <richh...@gmail.com>:

> This was discussed before, the new version never made it into a patch:
> http://groups.google.com/group/clojure/msg/43de40f078a291cc

Great!

The 'old' reductions behaves slightly different from the 'new'
reductions for the 3 argument form:
foo=> (reductions + 0 [3 5 10 1 2 7])
(0 3 8 18 19 21 28)
foo=> (reductions2 + 0 [3 5 10 1 2 7])
(3 8 18 19 21 28)

Which output is more correct? On the one hand supplying a preserved
'initial value' from outside does not make much sense, but on the
other hand perhaps it is more in step with 3 argument reduce.

Does it matter? Probably not. It does provide an interesting case
study. The 3 argument form could be considered just a helper to
achieve the 2 argument form, but because it is part of the public
interface people may chose to rely on it:

(defn left-total3 [coll]
(map list coll (reductions + 0 coll)))

might have been better written as
(defn left-total3 [coll]
(map list coll (cons 0 (reductions + coll))))
So is exposing the 3 argument version a bad thing? It is not very
idiomatic to use the alternatives:
(let-fn [(reducer [f acc coll] ...)]
(defn reductions [f coll] ... reducer ...))
And then again if I can call (reduce + 3 [1 2]) maybe it is reasonable
to call (reductions + 3 [1 2])
I'm over analyzing what is really a non-issue, but just found it
thought provoking.

Back to more practical concerns, attached is a modified version for
consideration which preserves the old behavior but is faster. Happy to
supply a git patch if on the right track - let me know what is best :)

Regards,
Tim.

[Rich Hickey]

On Wed, Dec 30, 2009 at 4:07 AM, Timothy Pratley
<timothy...@gmail.com> wrote:
> 2009/12/30 Rich Hickey <richh...@gmail.com>:
>> This was discussed before, the new version never made it into a patch:
>> http://groups.google.com/group/clojure/msg/43de40f078a291cc
>
> Great!
>
> The 'old' reductions behaves slightly different from the 'new'
> reductions for the 3 argument form:
>    foo=> (reductions + 0 [3 5 10 1 2 7])
>    (0 3 8 18 19 21 28)
>    foo=> (reductions2 + 0 [3 5 10 1 2 7])
>    (3 8 18 19 21 28)
>
> Which output is more correct?

The former.

> On the one hand supplying a preserved
> 'initial value' from outside does not make much sense, but on the
> other hand perhaps it is more in step with 3 argument reduce.
>
> Does it matter? Probably not. It does provide an interesting case
> study. The 3 argument form could be considered just a helper to
> achieve the 2 argument form, but because it is part of the public
> interface people may chose to rely on it:
>    (defn left-total3 [coll]
>     (map list coll (reductions + 0 coll)))
> might have been better written as
>    (defn left-total3 [coll]
>     (map list coll (cons 0 (reductions + coll))))
> So is exposing the 3 argument version a bad thing? It is not very
> idiomatic to use the alternatives:
> (let-fn [(reducer [f acc coll] ...)]
>  (defn reductions [f coll]  ... reducer ...))
> And then again if I can call (reduce + 3 [1 2]) maybe it is reasonable
> to call (reductions + 3 [1 2])
> I'm over analyzing what is really a non-issue, but just found it
> thought provoking.
>
> Back to more practical concerns, attached is a modified version for
> consideration which preserves the old behavior but is faster. Happy to
> supply a git patch if on the right track - let me know what is best :)
>
>

Great - thanks.

Rich