Examples of recursion, reduce, etc. for Clojure class.

index-except.clj

(ns cljclass)

;; Various ways to solve the problem of transforming a collection to a seq or vector of indices starting at zero, but
;; using an index of -1 for items for which (pred item) is true.
;; E.g. (index-except odd? [1 4 18 7 9 2 4 3]) => [-1 0 1 -1 -1 2 3 -1]

;; NB:
;; This is not the same as assigning indices and replacing the elements for which pred is true with -1.
;; E.g. (index-except odd? [1 2 3]) => [-1 0 -1] and not [-1 1 -1]. 


;; 1. Mutating solution. Not idiomatic. Not lazy.
(defn index-except [pred coll]
  (let [i (atom -1)]
    (for [item coll]
      (if (pred item)
          -1
          (swap! i inc)))))


;; 2. Recursion growing the stack. Not lazy.
(defn index-except-helper [pred coll i]
  (when-let [xs (seq coll)]
    (let [p (pred (first xs))]
      (cons (if p -1 i)
            (index-except-helper pred
                                 (rest xs)
                                 (if p i (inc i)))))))

(defn index-except [pred coll]
  (index-except-helper pred coll 0))


;; 3. Recursion with lazy-seq. Doesn't grow the stack. Very good solution.
(defn index-except-helper [pred coll i]
  (lazy-seq
    (when-let [xs (seq coll)]
      (let [p (pred (first xs))]
        (cons (if p -1 i)
              (index-except-helper pred
                                   (rest xs)
                                   (if p i (inc i))))))))

(defn index-except [pred coll]
  (index-except-helper pred coll 0))


;; 4. Optimized tail recursion. Doesn't grow the stack. Not lazy.
(defn index-except-helper [pred coll i acc]
  (if-let [xs (seq coll)]
    (let [p (pred (first xs))]
      (recur pred
             (rest xs)
             (if p i (inc i))
             (conj acc (if p -1 i))))
    acc))

(defn index-except [pred coll]
  (index-except-helper pred coll 0 []))


;; 5. Optimized tail recursion with no helper function. Doesn't grow the stack. Not lazy.
(defn index-except [pred coll]
  (loop [coll coll, i 0, acc []]
    (if-let [xs (seq coll)]
      (let [p (pred (first xs))]
        (recur (rest xs)
               (if p i (inc i))
               (conj acc (if p -1 i))))
      acc)))


;; 6. Using the reduce function instead of recursion. Not lazy.
(defn index-except [pred coll]
  (letfn [(f [[acc i] item]
            (let [p (pred item)]
              [(conj acc (if p -1 i))
               (if p i (inc i))]))]
    (first (reduce f [[] 0] coll))))


;; 7. Using the iterate function instead of recursion. Bad, don't do this! Not lazy.
(defn index-except [pred coll]
  (letfn [(f [[acc i xs]]
            (let [p (pred (first xs))]
              [(conj acc (if p -1 i))
               (if p i (inc i))
               (rest xs)]))]
    (let [xs (seq coll)]
      (-> (iterate f [[] 0 xs])
          (nth (count xs))
          first))))


;; 8. Crazy, inefficient solution with map-indexed and a hash map. Horrible, don't do this! Not lazy.
(defn index-except [pred coll]
  (let [xs (seq coll)
        m (->> xs
               (map-indexed vector)
               (remove (fn [[_ x]] (pred x)))
               (map-indexed #(vector (first %2) %1))
               (into {}))]
    (take (count xs)
          (map #(m % -1) (range)))))


;; 9. Using reductions to manage state like reduce would, but lazily.
;; The state is a pair: "value to return/produce" and "index for the next matching element".
(defn index-except [pred coll]
  (map first
       (rest (reductions (fn [[_ i] x]
                           (if (pred x)
                             [-1 i]
                             [i (inc i)]))
                         [nil 0], coll))))


;; 10. Using lazy-loop from https://github.com/flatland/useful/blob/develop/src/flatland/useful/seq.clj .
(defn index-except [pred coll]
  (lazy-loop [coll coll, i 0]
    (when-let [xs (seq coll)]
      (let [p (pred (first xs))]
        (cons (if p -1 i)
              (lazy-recur (rest xs) (if p i (inc i))))))))