Re: Tail-recursive lazy sequence construction by appending to the end of accumulator problem.

[Meikel Brandmeyer (kotarak)]

Hi,

I'm not sure I understand your problem. As soon as you talk about loop there is no laziness involved anymore. Then just use a vector. If you need laziness then use the usual lazy-seq approach with recursion (or if possible use higher-level sequence functions).

Kind regards
Meikel

[Tassilo Horn]

Alexander Semenov <boht...@gmail.com> writes:

Hi Alexander,

> One can create lazy sequences by wrapping each sequence element inside
> a 'lazy-seq' macro while constructing the sequence. Usually it's done
> with recursion. But what if I need a tail recursive construction of
> the sequence (using recur) accumulating results by appending them to
> the end of an accumulator. It just works using 'conj' and vector until
> 'lazy-seq' is added to the picture. It then breaks append to the end
> vector semantics and the result is now reversed. Here is an example
> (just for illustration - no real world value):

The difference is that conjoining to a list or seq prepends while it
appends for vectors. The lazy-seq wrapping in your example creates a
(lazy) seq from your vector, so the second-to-nth iteration of your loop
conjoins to a seq and thus prepends.

And there is no sense in having a lazy-seq in a loop-recur, because the
latter is inherently eager. Your accumulator will be a fully realized
lazy-seq. That is, the loop-recur defeats the purpose of lazy-seq,
i.e., defer the calculation of values until they are needed.

Although you say the example is only for illustration, it could be
written much more concise (and lazy) like so:

--8<---------------cut here---------------start------------->8---
user> (defn list-set [s n v]
(concat (take n s) [v] (drop (inc n) s)))
#'user/list-set
user> (list-set [0 1 2 3] 2 :foo)
(0 1 :foo 3)
user> (list-set (list 0 1 2 3) 2 :foo)
(0 1 :foo 3)
--8<---------------cut here---------------end--------------->8---

Bye,
Tassilo

[Alexander Semenov]

Hi, Tassilo.

On Thursday, July 12, 2012 9:22:11 AM UTC+3, Tassilo Horn wrote:

And there is no sense in having a lazy-seq in a loop-recur, because the
latter is inherently eager.  Your accumulator will be a fully realized
lazy-seq.  That is, the loop-recur defeats the purpose of lazy-seq,
i.e., defer the calculation of values until they are needed.

Although you say the example is only for illustration, it could be
written much more concise (and lazy) like so:

--8<---------------cut here---------------start------------->8---
user> (defn list-set [s n v]
        (concat (take n s) [v] (drop (inc n) s)))
#'user/list-set
user> (list-set [0 1 2 3] 2 :foo)
(0 1 :foo 3)
user> (list-set (list 0 1 2 3) 2 :foo)
(0 1 :foo 3)
--8<---------------cut here---------------end--------------->8---

Bye,
Tassilo

 
Oh, I see. I didn't realize the loop-recur eagerness - that's my fault. I'm pretty good in functional programming, though new to Clojure, so I knew how to accomplish the similar task using concat/take/drop/etc apparatus, but thanks anyway.

[Alexander Semenov]

What I still can't get is how does 'lazy-seq' prevent stack overflow. E.g.

(defn my-map [f coll] (when-let [s (seq coll)] (cons (f (first s)) (my-map f (rest s))))))
(nth (my-map inc (range 1000000)) 999999)
=> StackOverflowError

(defn my-map [f coll] (lazy-seq (when-let [s (seq coll)] (cons (f (first s)) (my-map f (rest s)))))))
(nth (my-map inc (range 1000000)) 999999)
=> 1000000

The second lazy approach still needs to traverse all the sequence recursively, why doesn't it cause stack overflow?

[Meikel Brandmeyer (kotarak)]

Hi,

in the first example the recursion happens immediately. That is when you call my-map you get start the recursion immediately all the way down. Hence you get the overflow. With lazy-seq basically nothing is done when calling my-map. The computation is deferred. Only when accessed the computation is done and then only one step, because the recursive call to my-map again defers any computation. The your call stack is always only one function deep. Instead of the 1million frames in the first version.

Hope this helps.

Kind regards
Meikel

[Alexander Semenov]

Hi, Meikel.

Got it, thank you.

[Steven E. Harris]

Alexander Semenov <boht...@gmail.com> writes:

> The second lazy approach still needs to traverse all the sequence
> recursively, why doesn't it cause stack overflow?

You might find my answer to the StackOverflow question "Thinking in Lazy
Sequences" useful here:

http://stackoverflow.com/a/2214049/31818

Note that I wrote it about a year and a half ago. I hope the references
to the Java classes are still correct.

--
Steven E. Harris