Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
416 PurelyFunctional.tv Newsletter

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.

@mchampine
Copy link

mchampine commented Mar 1, 2021

(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)))))

Loading

@jecneps
Copy link

jecneps commented Mar 1, 2021

Perfect time for transducers!

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

Loading

@steffan-westcott
Copy link

steffan-westcott commented Mar 1, 2021

Inspired by the answers already given:

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

Loading

@jaihindhreddy
Copy link

jaihindhreddy commented Mar 1, 2021

(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)))

Loading

@mchampine
Copy link

mchampine commented Mar 1, 2021

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

Loading

@steffan-westcott
Copy link

steffan-westcott commented Mar 1, 2021

@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)

Loading

@cloojure
Copy link

cloojure commented Mar 1, 2021

(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.

Loading

@werand
Copy link

werand commented Mar 1, 2021

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

Loading

@stuartstein777
Copy link

stuartstein777 commented Mar 1, 2021

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

Loading

@alex-gerdom
Copy link

alex-gerdom commented Mar 1, 2021

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))))))

Loading

@diavoletto76
Copy link

diavoletto76 commented Mar 1, 2021

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

Loading

@dfuenzalida
Copy link

dfuenzalida commented Mar 2, 2021

@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)

Loading

@charJe
Copy link

charJe commented Mar 2, 2021

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)))

Loading

@danieltdt
Copy link

danieltdt commented Mar 2, 2021

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

Loading

@cloojure
Copy link

cloojure commented Mar 2, 2021

@danieltdt - This one is my favorite!

Loading

@steffan-westcott
Copy link

steffan-westcott commented Mar 2, 2021

@danieltdt I like it!

Loading

@vmpj
Copy link

vmpj commented Mar 2, 2021

(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))))))))

Loading

@diavoletto76
Copy link

diavoletto76 commented Mar 2, 2021

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

Loading

@miner
Copy link

miner commented Mar 2, 2021

(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))

Loading

@simbiotiqu
Copy link

simbiotiqu commented Apr 11, 2021

(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)))

Loading

@dlidstrom
Copy link

dlidstrom commented Jun 20, 2021

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>

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment