Monday, 15 December 2008

99 Problems in Lisp (Part II)

P06 - Find out whether a list is a palindrome?

(defn palindrome? [x]
(= x (reverse x)))

P07 -Flatten a nested list structure.

(defn atom? [x]
(or (nil? x) (not (seq? x))))

;; Not tail recursive and generally makes me feel sick that I've even typed
;; such a monstrosity!
(defn my-flatten [list]
(if (atom? list)
(if (atom? (first list))
(cons (first list) (my-flatten (rest list)))
(concat (my-flatten (first list)) (my-flatten (rest list))))))

The above feels yucky! Using the example from the Haskell puzzles we can come up with a much cleaner solution.

How'd you flatten a list? If it's an atom then we're done (list x), whereas if it's a list then we want to flatten each element in turn (mapcat my-flatten2 x). This makes a really simple definition as below:

(defn my-flatten2 [x]
(if (atom? x)
(list x)
(mapcat my-flatten2 x)))

mapcat is similar to the map function but collects all of the items together with concatenation. It takes a function and a series of lists as arguments, for example:

user> (mapcat (fn [x y] (list (+ x y))) '(1 2 3) '(3 4 5))
(4 6 8)