320 - PurelyFunctional.tv Newsletter - Puzzle - Remove nth element

00 Description.md

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.

Alan Thompson.clj

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

Eric Normand.clj

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

Francisco Vides Fernández.clj

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

Nathan Donolli.clj

(defn remove-at [n xs]
  (let [removed (flatten (conj (drop (+ n 1) xs)(take n xs)))]
    (if (vector? xs)
      (vec removed)
      removed)))

Neil McCallum.clj

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

Peter Strömberg.clj

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

Steve Miner.clj

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