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!