On Fri, Dec 5, 2008 at 9:55 PM, Chouser <[EMAIL PROTECTED]> 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
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
