## Saturday 20 December 2008

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