<< Back to previous view

[CLJ-1218] mapcat is too eager Created: 16/Jun/13  Updated: 02/May/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.5
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Gary Fredericks Assignee: Unassigned
Resolution: Unresolved Votes: 4
Labels: lazy

Attachments: Text File CLJ-1218-lazier-mapcat.patch    
Patch: Code and Test


The following expression prints 1234 and returns 1:

(first (mapcat #(do (print %) [%]) '(1 2 3 4 5 6 7)))

The reason is that (apply concat args) is not maximally lazy in its arguments, and indeed will realize the first four before returning the first item. This in turn is essentially unavoidable for a variadic concat.

This could either be fixed just in mapcat, or by adding a new function (to clojure.core?) that is a non-variadic equivalent to concat, and reimplementing mapcat with it:

(defn join
  "Lazily concatenates a sequence-of-sequences into a flat sequence."
  (lazy-seq (when-let [[x & xs] (seq s)] (concat x (join xs)))))

Comment by Gary Fredericks [ 17/Jun/13 7:54 AM ]

I realized that concat could actually be made lazier without changing its semantics, if it had a single [& args] clause that was then implemented similarly to join above.

Comment by John Jacobsen [ 27/Jul/13 8:08 AM ]

I lost several hours understanding this issue last month [1, 2] before seeing this ticket in Jira today... +1.

[1] http://eigenhombre.com/2013/07/13/updating-the-genome-decoder-resulting-consequences/

[2] http://clojurian.blogspot.com/2012/11/beware-of-mapcat.html

Comment by Gary Fredericks [ 05/Feb/14 1:35 PM ]

Updated join code to be actually valid.

Comment by Ghadi Shayban [ 21/May/15 8:32 PM ]

The version of join in the description is not maximally lazy either, and will realize two of the underlying collections. Reason: destructuring the seq results in a call to 'nth' for 'x' and 'nthnext' for 'xs'. nthnext is not maximally lazy.

(defn join
  "Lazily concatenates a sequence-of-sequences into a flat sequence."
   (when-let [s (seq s)] 
     (concat (first s) (join (rest s))))))
Comment by Ghadi Shayban [ 02/May/17 10:47 AM ]

Though the docstring makes no lazyiness promises (except declaring its specific implementation), this seems like a defect, not an enhancement. mapcat realizes 4 underlying collections at minimum:

boot.user=> (defn notifying-seq [cb!] (lazy-seq (cb!) (cons :ignored (notifying-seq cb!))))                                                              


boot.user=> (let [a (atom 0)] 
  (seq (mapcat (constantly [:ignored :ignored])
               (notifying-seq #(swap! a inc))))
Generated at Tue Jan 16 23:45:36 CST 2018 using JIRA 4.4#649-r158309.