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