partition_by.clj

;; Spec: split a list into chunks such that the total size of each chunk is limited.
;; Size is measured by a function parameter.
;; Output should be a lazy sequence.
(comment
  (partition-by :size 10 [{:size 1} {:size 2} {:size 8} {:size 3} {:size 7}])
    ;; ==> (({:size 1} {:size 2}) ({:size 8}) ({:size 3} {:size 7}))
  )

;; First implementation: reductions seems like a good fit, but requires too much scaffolding
(defn partition-by [measure limit xs]
  (let [sizes (map measure xs)
        pairs (map vector (range) (reductions + sizes))
        i (first (first (filter (fn [[_ siz]] (> siz limit)) pairs)))]
    (if i
      (let [j (max 1 i)] ; always take at least 1 element
        (lazy-seq
         (cons (take j xs)
               (esko measure limit (drop j xs)))))
      (list xs))))

;; Second implementation: let's emulate an imperative loop
(defn partition-by [measure limit xs]
  (loop [xs xs
         size 0
         chunk []]
    (cond
      (empty? xs)
      (list chunk)
      
      (> (+ size (measure (first xs))) limit)
      (lazy-seq
       (cons chunk (esko measure limit xs)))
      
      :else
      (recur (rest xs)
             (+ size (measure (first xs)))
             (conj chunk (first xs))))))

;; Third implementation: let's try to find a new primitive that will let us express partition-by
(defn take-while-reduce
  "Return the longest prefix of coll such that
     (pred (reduce f init prefix)) ==> true"
  [pred f init coll]
  (when-let [s (seq coll)]
    (let [[x & xs] s
          updated (f init x)]
      (when (pred updated)
        (lazy-seq
         (cons x (take-while-reduce pred f updated xs)))))))

(defn partition-by [measure limit coll]
  (when-let [s (seq coll)]
    (let [chunk (take-while-reduce (partial >= limit)
                                   (fn [siz x] (+ siz (measure x)))
                                   0
                                   s)]
      (lazy-seq
       (cons chunk (esko measure limit (drop (count chunk) s)))))))