Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
320 - PurelyFunctional.tv Newsletter - Puzzle - Remove nth element

remove the nth element from a list

Clojure's two main sequences, lists and vectors, do not easily let you remove an item from the collection when that item is in the middle of the sequence. Sometimes we need to do that. Write a function remove-at that removes the element at position n from a sequence.

(remove-at 3 [1 2 3 4 5 6])
; => (1 2 3 5 6)

Make this robust. You'll have to make some hard design decisions like how to handle the empty sequence, how to handle out-of-bounds n, and more.

Bonus points for clarity and efficiency. But the #1 priority is completeness and correctness. Please document your choices in comments.

Extra credit: write a separate version for sequences and for vectors. The vector version should take and return vectors.

(s/defn drop-at :- tsk/List
"Removes an element from a collection at the specified index."
[coll :- tsk/List
index :- s/Int]
(when (neg? index)
(throw (ex-info "Index cannot be negative " index)))
(when (<= (count coll) index)
(throw (ex-info "Index cannot exceed collection length: " {:length (count coll) :index index})))
(glue (take index coll)
(drop (inc index) coll)))
;; We want it to throw when index is out of bounds.
;; We want it to work with infinite sequences.
;; We want it to be special-cased for vectors
(defn drop-nth-seq [n coll]
(when (empty? coll)
(throw (IndexOutOfBoundsException. "n is too large")))
(when (neg? n)
(throw (IndexOutOfBoundsException. "n is negative")))
(if (zero? n)
(next coll)
(lazy-seq
(cons (first coll)
(drop-nth-seq (dec n) (next coll))))))
(defn drop-nth-vec [n v]
(into (subvec v 0 n) (subvec v (inc n))))
(defn drop-nth [n coll]
(if (vector? coll)
(drop-nth-vec n coll)
(drop-nth-seq n coll)))
;; Design choice: let clojure manage all design choices :P
(defn remove-at [n coll]
(concat (take n coll) (drop (inc n) coll)))
(defn vector-remove-at [n coll]
(into [] (remove-at n coll)))
(defn remove-at [n xs]
(let [removed (flatten (conj (drop (+ n 1) xs)(take n xs)))]
(if (vector? xs)
(vec removed)
removed)))
(defn remove-at
"Incoming seq less element at pos n. Removing out of range is a null op"
[n coll]
(concat
(take n coll)
(nthrest coll (inc n))))
(defn vec-remove-at
[n coll]
{:pre [(vector? coll)]}
(vec (remove-at n coll)))
(defn remove-at [n c]
((if (vector? c) (comp vec concat) concat) (take n c) (drop (inc n) c)))
(defn remove-at [n c]
((if (vector? c) (comp vec (partial remove nil?)) (partial remove nil?))
(map-indexed (fn [i item] (when (not= i n) item)) c)))
(defn remove-at [n c]
(let [f (lazy-cat (repeat n identity) [(fn [_] nil)] (repeat (dec (count c)) identity))]
(remove nil? (map (fn [item f] (f item)) c f))))
;; I wrote several implementations. The `n` must be a fixed precision integer,
;; and the `coll` must be seqable (typically a list or a vector). If n is
;; negative or greater than the last index of the collection, I just return
;; the whole collection rather than throwing an error. The `remove-at-vec` is
;; specialized for vector input and output. It’s faster, but eager. It seems
;; like this might be useful as a transducer so I implemented that as my
;; preferred solution. It’s also lazy.
;; Classic seq style
(defn remove-at-coll [n coll]
{:pre [(int? n) (seqable? coll)]}
(concat (take n coll) (drop (inc n) coll)))
;; Specialized for vectors. Not lazy. Returns whole vector if index is out of bounds.
(defn remove-at-vec [n v]
{:pre [(int? n) (vector? v)]}
(if (< -1 n (count v))
(into (subvec v 0 n) (subvec v (inc n)))
v))
;; Transducer version
(defn remove-at
"Returns a lazy sequence of the elments of the collection `coll` with the element at index
`n` removed. Returns a stateful transducer when no collection is provided."
([n]
{:pre [(int? n)]}
(fn [rf]
(let [nv (volatile! n)]
(fn
([] (rf))
([result] (rf result))
([result input]
(let [n @nv]
;; n=0 on input to skip
(cond (pos? n) (do (vswap! nv unchecked-dec) (rf result input))
(zero? n) (do (vreset! nv -1) result)
:else (rf result input))))))))
([n coll]
{:pre [(int? n) (seqable? coll)]}
(sequence (remove-at n) coll)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.