partition.clj

(ns lazy.partition)

;; returns tuple: [(take-while pred coll) rest-of-coll]
(defn split-with [acc pred coll]
  (lazy-seq
   (let [h (first coll)]
     (if (and h (pred h))
       (split-with (lazy-cat acc [h]) pred (rest coll))
       [acc coll]))))

(defn lazy-partition-by [f coll]
  (lazy-seq
   (when-let [s (seq coll)]
     (let [v (f (first s))
           ;; Need coordination here, since we don't know if
           ;; the car has been realised by the time we want to start
           ;; consuming cdr
           sp (delay (split-with () #(= (f %) v) s))]
       (cons (first @sp)
             (lazy-partition-by f (second @sp)))))))

(let [big-seq (repeatedly 1000000 #(rand-int 10))
      very-lazy-seq (lazy-partition-by even? big-seq)]
  (assert (instance? clojure.lang.LazySeq very-lazy-seq))
  (assert (every? #(instance? clojure.lang.LazySeq %) (take 10 very-lazy-seq))))

;; BROKEN
;; (let [big-seq-two (mapcat (fn [_] (repeat (rand-int 100) (rand-int 10))) (range 10000))]
;;  (lazy-partition-by odd? big-seq-two))

;; ----------------------------------------------------------------------------------------

;; mutation saves (??) the day

(defn take-while! [pred coll]
  (lazy-seq
   (let [h (first @coll)]
     (when (and h (pred h))
       (swap! coll next)
       (cons h (take-while! pred coll))))))

(defn lazy-partition-helper [f coll]
  (lazy-seq
   (when-let [h (-> @coll seq first)]
     (let [v      (f h)
           subseq (take-while! #(= (f %) v) coll)]
       #_(prn :coll @coll)
       (cons subseq
             (do (when-not (realized? subseq) (dorun subseq))
                 (lazy-partition-helper f coll)))))))


(defn lazy-partition-by-2 [f coll]
  (lazy-partition-helper f (atom coll)))

(let [big-seq (repeatedly 1000000 #(rand-int 10))
      very-lazy-seq (lazy-partition-by-2 even? big-seq)]
  (assert (instance? clojure.lang.LazySeq very-lazy-seq))
  (assert (every? #(instance? clojure.lang.LazySeq %) (take 10 very-lazy-seq))))

(let [big-seq-two       (mapcat (fn [_] (repeat (rand-int 10000) (rand-int 10)))
                                (range 10000))
      very-lazy-seq-two (lazy-partition-by-2 odd? big-seq-two)]
  (assert (instance? clojure.lang.LazySeq very-lazy-seq-two))
  (assert (every? #(instance? clojure.lang.LazySeq %) (take 10 very-lazy-seq-two))))

Overflows the stack if the subsequences are large!

Version 2 works at the cost of introducing an atom into the mix.