Clojure “concat” not being lazy

Question

I have been testing concat behaviour.

The docstring says:

Returns a lazy seq representing the concatenation of the elements in the supplied colls.

However, it seems that concat does not behave lazily for its arguments. Instead we observe the usual eager evaluation. This is not what I would expect.

Observe:

Here is simple code to generate a binary tree holding integers from "The Joy of Clojure, 2nd edition", p. 208:

; we have a binary tree based on records, holding a val and having left
; and right subtrees

(defrecord TreeNode [val left right])

; xconj basically is insertion sort; inserts value v into tree t. 
; + The code in JoC is more compact; here, "explicited" for readability.

(defn xconj [t v]
   (cond
      (nil? t)            (TreeNode. v nil nil)
      (< v (get t :val))  (TreeNode. (get t :val)
                                     (xconj (get t :left) v)
                                     (get t :right))
      :else               (TreeNode. (get t :val)
                                     (get t :left)
                                     (xconj (get t :right) v))))

; Convert a tree into a seqs (in-order traversal, so the seq will spit 
; out the integers in order sorted ascending).
; Returns a lazy seq as "concat" returns clojure.lang.LazySeq
; + The code in JoC is more compact; here, "explicited" for readability.

(defn xseq [t]
   (when (some? t)
      (concat (xseq (get t :left))
              [ (get t :val) ]
              (xseq (get t :right)))))

; "xseq" is a bit mute; add some printout to probe behaviour (watching
; out to not destroy laziness when doing so)

(defn xseq-p1 [t k]
   (if (nil? t) (println k "▼" "⊥") (println k "▼" (get t :val)))
   (when (some? t)
      (concat (xseq-p1 (get t :left) (str k "[" (get t :val) "]" "◀"))
              [ (get t :val) ]
              (xseq-p1 (get t :right) (str k "[" (get t :val) "]" "▶")))))

; create a tree for testing

(def ll (reduce xconj nil [3 5 2 4 6]))

Now, querying the type of the value returned by xseq-p1 shows that it traverses the whole tree?!

([3]◀[2]▶ ▼ ⊥ means found 3, went left, found 2, went right, now at nil)

(type (xseq-p1 ll ""))
; ▼ 3
; [3]◀ ▼ 2
; [3]◀[2]◀ ▼ ⊥
; [3]◀[2]▶ ▼ ⊥
; [3]▶ ▼ 5
; [3]▶[5]◀ ▼ 4
; [3]▶[5]◀[4]◀ ▼ ⊥
; [3]▶[5]◀[4]▶ ▼ ⊥
; [3]▶[5]▶ ▼ 6
; [3]▶[5]▶[6]◀ ▼ ⊥
; [3]▶[5]▶[6]▶ ▼ ⊥
; clojure.lang.LazySeq

Making xseq actually lazy demands an additional lazy-seq in front of concat:

(defn xseq-p2 [t k]
   (if (nil? t) (println k "▼" "⊥") (println k "▼" (get t :val)))
   (when (some? t)
      (lazy-seq
      (concat (xseq-p2 (get t :left) (str k "[" (get t :val) "]" "◀"))
              [ (get t :val) ]
              (xseq-p2 (get t :right) (str k "[" (get t :val) "]" "▶"))))))

Now it is lazy:

(type (xseq-p2 ll ""))
; ▼ 3
; clojure.lang.LazySeq

(take 2 (xseq-p2 ll ""))
; ▼ 3
; ([3]◀ ▼ 2
; [3]▶ ▼ 5
; [3]◀[2]◀ ▼ ⊥
; [3]◀[2]▶ ▼ ⊥
; 2 3)

Is this expected?

P.S.

An alternative is to lazify either both descents (or just the rightwards one). With both descents lazified, xseq-p3 is even lazier than xseq-p1:

(defn xseq-p3 [t k]
   (if (nil? t) (println k "▼" "⊥") (println k "▼" (get t :val)))
   (when (some? t)
      (let [ left   (get t :left)
             v      (get t :val)
             right  (get t :right)
             l-seq  (lazy-seq (xseq-p3 left  (str k "[" v "]" "◀")))
             r-seq  (lazy-seq (xseq-p3 right (str k "[" v "]" "▶"))) ]
         (concat l-seq [v] r-seq))))

(type (xseq-p3 ll ""))
; ▼ 3
; clojure.lang.LazySeq

(take 2 (xseq-p3 ll ""))
; ▼ 3
; ([3]◀ ▼ 2
; [3]◀[2]◀ ▼ ⊥
; [3]◀[2]▶ ▼ ⊥
; 2 3)

@glts Ah yes, using lazy-cat instead of cat in xseq-p1 makes it behave like xseq-p3! That's a win. But then what is "lazy" about concat? I would say, it only behaves lazily if its arguments were lazy in the first place. — David Tonhofer

Alan Thompson Alan Thompson · Accepted Answer · 2019-08-14T16:55:13

Any expression passed as an argument to a Clojure function is evaluated eagerly, so the function code sees only a single value. It could be primitive (e.g. 42) or a built-in (e.g. "hello") or a composite value (e.g. [42 "hello" {:a 1 :b 2}]). That value might be a lazy sequence like that produced by (range).

Note that if you type (take 3 (range)) the take function does not see the (range) part. It looks instead like (take 3 <lazy-seq-produced-by-range>). So the function call in the expression (range) is eagerly evaluated, and the lazy-seq it produces is passed to the take expression.

If an arg is a lazy sequence, the function itself is unaware of this. You could instrument the generating lazy seq with println etc to observe timing, but that won't affect how the function uses a value via (first arg), (nth arg 3), etc. Normally, you only care about how a function generates a lazy result, and perhaps about how many elements of an input sequence it consumes (lazy or not).

You should also be aware that most lazy sequences in Clojure operate in length-32 chunks for efficiency. This means that a lazy sequence can actually do more work than desired. For example, suppose you only want to consume 3 "expensive" items from a lazy sequence. Since chunking will normally generate 32 items when you request the first item, you have done unnecessary and unwanted extra work.

I normally avoid lazy sequences, as they are unpredictable in when then will run and how many items in the sequence will be realized. Thus, I always use mapv, filterv & friends, and wrap other things with (vec ...) a lot (I have my own non-lazy forv, for example). I only use lazy sequences when the input/output is truly "large" (e.g. processing every row in a large DB table).

Clojure “concat” not being lazy

1 Answers