reductions.clj

(ns-unmap *ns* 'reductions)

;; definition of reductions:
;;
;;   (reductions f y_0 (x_1 ... x_n)) = (y_0 y_1 ... y_n)
;;
;;       where y_i = (f y_{i-1} x_i)

;; invariant A:
;;
;;   reds = (y_0 y_1 ... y_i)
;;   red  = y_i
;;   vals = (x_{i+1} ... x_n)

;; invariant B:
;;
;;   reds = (y_0 y_1 ... y_{i-1})
;;   red  = y_i
;;   vals = (x_{i+1} ... x_n)

;; eager, letfn, invariant A
(defn reductions [f init coll]
  (letfn [(step [reds red vals]
            (if (empty? vals)
              (seq reds)
              (let [next-red (f red (first vals))]
                (recur (conj reds next-red)
                       next-red
                       (rest vals)))))]
    (step [init] init coll)))

;; eager, letfn, invariant B
(defn reductions [f init coll]
  (letfn [(step [reds red vals]
            (if (empty? vals)
              (seq (conj reds red))
              (recur (conj reds red)
                     (f red (first vals))
                     (rest vals))))]
    (step [] init coll)))

;; eager, loop, invariant A
(defn reductions [f init coll]
  (loop [reds [init]
         red init
         vals coll]
    (if (empty? vals)
      (seq reds)
      (let [next-red (f red (first vals))]
        (recur (conj reds next-red)
               next-red
               (rest vals))))))

;; eager, loop, invariant B
(defn reductions [f init coll]
  (loop [reds []
         red init
         vals coll]
    (if (empty? vals)
      (seq (conj reds red))
      (recur (conj reds red)
             (f red (first vals))
             (rest vals)))))

;; lazy, letfn, "invariant A"
(defn reductions [f init coll]
  (letfn [(step [red vals]
            (lazy-seq
              (when (seq vals)
                (let [next-red (f red (first vals))]
                  (cons next-red
                        (step next-red (rest vals)))))))]
    (cons init (step init coll))))

;; lazy, letfn, "invariant B"
(defn reductions [f init coll]
  (letfn [(step [red vals]
            (lazy-seq
              (if (empty? vals)
                [red]
                (cons red (step (f red (first vals))
                                (rest vals))))))]
    (step init coll)))

;; lazy, "invariant B"
(defn reductions [f red vals]
  (lazy-seq
    (if (empty? vals)
      [red]
      (cons red (reductions f
                            (f red (first vals))
                            (rest vals))))))