Haskell's scanl

[Alex Baranosky]

My friend's playing with Haskell, and asked me how I'd write a function to take a list and return a list of the sums like so:

(f [1 2  4 8]) 

=> [1 3 7 15]

So I told him about Haskell's scanl function.

Is scanl available in Haskell?

These were my two versions of it and some simple benchmarks:

(defn scanl

  ([f seed coll]

    (scanl f seed coll 1))

  ([f seed coll i]

    (if (<= i (count coll))

      (cons (reduce f seed (take i coll))

        (scanl f seed coll (inc i))))))

(println (scanl + 0 [1 4 5 9]))

(defn scanl2 [f seed coll]

  (loop [f f seed seed coll coll acc []]

    (let [cnt (count acc)]

      (if (< cnt (count coll))

        (recur f seed coll (conj acc (reduce f seed (take (inc cnt) coll))))

        acc))))

(println (scanl2 + 0 [1 4 5 9]))

(def first (with-out-str (time (scanl + 0 [1 4 5 9 6 7 8 9]))))

(def second (with-out-str (time (scanl2 + 0 [1 4 5 9 6 7 8 9]))))

(println first)

(println second)

[Chris Maier]

That sounds like 'reductions':

(reductions + [1 2 4 8])
==> (1 3 7 15)

Chris

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

[Ken Wesson]

On Wed, Dec 1, 2010 at 10:25 PM, Chris Maier
<christop...@gmail.com> wrote:
> That sounds like 'reductions':
>
> (reductions + [1 2 4 8])
> ==> (1 3 7 15)

On top of that, both the OP's algorithms are quadratic.

(defn scanl2 [f seed coll]

(loop [ttl seed [fst & rst] coll acc []]
(let [ttl (f ttl fst)
acc (conj acc ttl)]
(if rst
(recur ttl rst acc)
acc))))

is not, but it's not lazy. The above loop can be transformed
relatively trivially into a lazy-seq use that would be lazy;
reductions may be implemented similarly to such a lazy-seq use.