Stack overflow with lazy-seq

Question

I'm learning Clojure by doing problems from rich4clojure repo. Problem 147 asks one to create a function which returns a lazy sequence of rows following rules of Pascal triangle given initial row. For example, for [3 1 2], the next row is [3 4 3 2]. Here's my solution:

(defn pascal
      ([row] (lazy-seq (cons row (__ row :next))))
      ([row _]
       (lazy-seq
        (let [next-row (map #(apply +' %) (partition 2 1 (concat '(0) row '(0))))]
          (cons next-row (pascal next-row :next)))))))

I decided to test it and compare it with solutions others came up with. For example, one user wrote:

(defn pascal [coll]
(lazy-seq
  (cons coll
        (pascal (let [middle (map #(apply +' %) (partition 2 1 coll))]
                       (concat [(first coll)] middle [(last coll)]))))))

I time both solutions by evaluating:

time (nth (nth (pascal [1]) 400) 50))

and it turns out that mine is faster (which is sort of expected because the other user relies on last which is O(n)). However, when I try to calculate 1000th row, I get stack overflow error only in case of my function. I'm struggling to see why this happens because I shouldn't be increasing the stack size. What am I missing?

Comments

It's hard to say with that formatting (this website doesn't support multiline code in backticks, you have to use the designated Code Block button in the UI) and some `__` in the code, but it might be this: https://stuartsierra.com/2015/04/26/clojure-donts-concat

---

Sorry about that, I fixed it now.

---

@Eugene Pakhomov
I think I see why this causes problems, but I don't see how other solution is different i.e. why there's no stack overflow there..

---

Not a trivial thing to reason about (partly why `concat` can be hard to use safely) and you can get the same behavior even without `concat` by replacing that `partition` call with `(partition-all 2 1 (cons 0 row))` (should be equivalent in terms of the non-exceptional result).

Unfortunately I can't add more details without having to delve much deeper into the implementation details of the built-in functions to figure it all out. But an easy fix here is to replace `map` with `mapv` or replace that `partition` call with `(partition-all 2 1 (into [0] row))`. Of course, it makes rows eager, and there's probably a solution that avoids that but it's too late in the day for me to think about it.

---

Ah, of course - their solution doesn't fail because it uses `(last coll)`. So the collection is already fully realized before it's fed into another `lazy-seq`. In the end, their solution is also eager at the row level. You original solution is not eager, but its very implementation pays for it with blown up stacks.

---

Oh I think I see now, but I will definitely have to think more about it. Anyway, thank you very much for your help, I really appreciate it!

---

I reworked the code a bit to get  something which doesn't blow the stack.

       (defn pascal
            "Successive rows of Pascal's triangle as a lazy seq."
            [row]
            (lazy-seq
             (cons (seq row) ;; For consistency of output
                   (pascal
                    (cons (first row)
                          (map (partial apply +') (partition-all 2 1 row)))))))

This solution when run in a `(do (dorun (take n ...)) nil)` code block, to make sure emacs doesn't choke on the output gives me a nice "out of heap" when n = 50 million.

The reason is `concat` for the reasons mentioned in the above linked article.

First of all, I call `seq` on row because else the first row returned will be of collection type of the input, while the rest is seqs. Lazy-seq mostly ends up on the outside of the code body.

Practicing recursive strategies helps a lot. It's not immediately obvious for current day programmers why the recusive call is where it is.

As you see, it's also worth revisiting a cheat sheet from time to time to see what functions you actually know, but seldom ever use and play around with them to get a feel for when to use them. `partition-all` makes quite the difference here.