99 Problems in Lisp (Part V)

I think that the style I have of using recur is probably very wrong. concat must be O(N) (since the only way to get to the end of the list is to walk it). I'm making N calls to it, so most of the code I've written is probably O(N^2).


P13 encode it directly

(defn encode-direct [lst]
  ((fn [xs accum]
     (if (= nil xs)
       accum
       (recur (drop-while (fn [x] (= x (first xs))) xs)
       (let [items (take-while (fn [x] (= x (first xs))) xs)]
  (if (= 1 (count items))
    (concat accum items)
    (concat accum (list (list (count items) (first items))))))))) lst nil))

P14 Duplicate the elements of a list

(defn dupli [lst]
  (mapcat (fn [x] (list x x)) lst))

P15 Replicate the elements of a list a given number of times

(defn repli [lst n]
  (mapcat (fn [x] (replicate n x)) lst))

P16 Drop every nth element from a list

(defn drop-nth [lst n]
  ((fn [xs i accum]
     (if (= nil xs)
       accum
       (if (= 0 (rem i n))
  (recur (rest xs) (inc i) accum)
  (recur (rest xs) (inc i) (concat accum (list (first xs))))))) lst 1 nil))

P17 split a list into two parts

(defn split [lst n]
  (list (take n lst) (drop n lst)))

P18 extract a slice from a list

(defn slice [lst i n]
  (take (inc (- n i)) (drop (dec i) lst)))