416 PurelyFunctional.tv Newsletter

00 Index filter.md

Index filter

Clojure already has a function called filter. You pass it a predicate and it calls the predicate on each element. But what it doesn't have is a function called filter-index that calls a predicate on the indexes of the sequence to decide what to keep.

Examples

(filter-index even? "abcdefg") ;=> (\a \c \e \g) (keep even-indexed elements)
(filter-index prime? "abcdefghijk") ;=> (\c \d \f \h) (keep prime-number indexes)

Thanks to this site for the challenge idea where it is considered Hard in Python. The problem has been modified from the original.

Please submit your solutions as comments on this gist.

(defn filter-index [pred s]
  (map second (filter #(pred (first %)) (map-indexed vector s))))

or

(defn filter-index [pred s]
  (map (partial get s) (filter pred (range (count s)))))

Perfect time for transducers!

(defn filter-index [f coll]
  (-> (comp
          (map-indexed vector)
          (filter (fn [[i x]] (f i)))
          (map second))
        (eduction coll)))

Inspired by the answers already given:

(defn filter-index [pred coll]
  (eduction (map-indexed vector)
            (filter (comp pred first))
            (map second)
            coll))

(defn filter-index [f coll]
  (keep-indexed #(when (f %) %2) coll))

And in Python:

def filter_index(f, coll):
    return [x for i, x in enumerate(coll) if f(i)]

Edit: as pointed out by @steffan-westcott, the Clojure impl above is broken, because it eats all nils in coll. Here's a correct impl:

(defn filter-index
  ([pred]
    (fn [rf]
      (let [iv (volatile! -1)]
        (fn
          ([] (rf))
          ([result] (rf result))
          ([result input]
            (if (pred (vswap! iv inc))
                (rf result input)
                result))))))
  ([pred coll]
    (sequence (filter-index pred) coll)))

Implements a transducer-returning arity, and uses clojure.core/sequence to get the chunked laziness for free.

Edit2: Of course, we can use map-indexed with vector, but the above impl avoids the overhead of creating one vector per element:

(defn filter-index
  ([pred]
    (comp (map-indexed vector)
          (filter #(pred (nth % 0)))
          (map #(nth % 1))))
  ([pred coll]
    (sequence (filter-index pred) coll)))

@jaihindhreddy nice! Very concise. I was trying to think of a way to use keep-indexed and that's perfect.

@jaihindhreddy keep-indexed discards all nil results, which is a problem in cases where we need to keep them.
For example, (filter-index even? [nil nil nil]) should return (nil nil)

(ns tst.demo.core
  (:use tupelo.core tupelo.test))

(defn filter-index
  [pred vals]
  (let [idx-vals     (map vector (range) vals)
        idx-filtered (filter (fn [[idx val]]
                               (pred idx))
                       idx-vals)
        result       (mapv second idx-filtered)]
    result))

(dotest
  (is= [\a \c \e \g] (filter-index even? "abcdefg")))

I forgot about map-indexed, but I like to show the intermediate steps.

(defn filter-index [pred s]
  (->> (map vector (range) s)
       (filter #(pred (first %)))
       (map second)))

(defn filter-index-2 [f xs]
  (->> (zipmap (range (count xs)) xs)
       (sort-by key)
       (filter (fn [[k _]] (f k)))
       (vals)))

Came up with basically the same solution as werand.

(defn filter-index [pred coll]
  (->> (map vector (range) coll)
       (filter #(pred (first %)))
       (map second)))

So here's one as a lazy-seq just for fun:

(defn filter-index
  ([pred coll] (filter-index pred coll 0))
  ([pred coll ix]
   (lazy-seq
    (cond (empty? coll) nil
          (pred ix) (cons (first coll)
                          (filter-index pred (rest coll) (inc ix)))
          :else (filter-index pred (rest coll) (inc ix))))))

(defn filter-index [f xs]
  (->> (map-indexed vector xs)
       (filter (comp f first))
       (map second)))

@diavoletto76: wow, I wrote to the exact same implementation :-)

(defn filter-index [f xs]
  (->> (map-indexed vector xs)
       (filter (comp f first))
       (map second)))

(defn prime? [n] ;; Mock version
  (#{2 3 5 7 11 13} n))

;; (filter-index even? "abcdefg") ;; => (\a \c \e \g)
;; (filter-index prime? "abcdefghijk") ;; => (\c \d \f \h)

I know we are supposed to be clojure fanatics here, but here is a common lisp solution that returns the same type as the input:

(import 'arrows:-<>>)

(defun keep-if-index (predicate sequence)
  (-<>> (loop for i from 0 below (length sequence) collect i)
    (map 'list 'list sequence)
    (remove-if-not predicate <> :key 'second)
    (map (class-of sequence) 'first)))

(defn filter-index
  [f coll]
  (for [[i e] (map-indexed list coll) :when (f i)] e))

@danieltdt - This one is my favorite!

@danieltdt I like it!

(defn filter-index 
  ([pred coll]
    (filter-index pred coll 0))
  ([pred coll index]
    (lazy-seq
      (when-let [s (seq coll)]
        (let [f (first s) r (rest s)]
          (if (pred index)
            (cons f (filter-index pred r (inc index)))
            (filter-index pred r (inc index))))))))

@danieltdt Oh my God, even names of function parameters are identical ;)

(defn filter-index [pred coll]
  (sequence (keep-indexed (fn [i x] (when (pred i) x))) coll))

Note this doesn't work with coll containing nils, as pointed out by @steffan-westcott

Here's a variation that works with nils

(defn xfin [pred coll]
  (sequence (comp (keep-indexed (fn [i x] (when (pred i) (list x))))
                  cat)
            coll))

(defn index-tuples [coll]
  (loop [c 0
         rst coll
         acc []]
    (if (empty? rst)
      acc
      (recur (inc c)
             (drop 1 rst)
             (conj acc [c
                        (first rst)])))))

(defn filter-index [f coll]
  (->> coll
       index-tuples
       (filter (fn [[i _]] (f i)))
       (map second)))

let filterIndex pred seq = // (int -> bool) -> seq<'a> -> seq<'a>
    seq // seq<'a>
    |> Seq.zip [ 1 .. Seq.length seq ] // seq<int * 'a>
    |> Seq.where (fst >> pred) // seq<int * 'a>
    |> Seq.map snd // seq<'a>