This is where things got both fun and difficult. These problems aren’t too difficult in F# and scala, but flatten especially confused me. Luckily, I found an example of LISP that used the mapcat function, and it basically wrote the flatten function for me. Map maps a function to a list, but mapcat assumes that the function applied to the list turns each element into a list, and then concatenates all of the items into a new list. It was confusing to say the least, but I am starting to see the power of it peeking around the corner.
; P07 (**) Flatten a nested list structure. (defn flatten [l] (if (list? l) (mapcat flatten l) (list l))) ; P08 (**) Eliminate consecutive duplicates of list elements. (comment "If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.") (defn compress [l] (loop [current '() remaining l] (if (nil? (first remaining)) (reverse current) (recur (if (= (first current) (first remaining)) current (cons (first remaining) current)) (rest remaining))))) ; P09 (**) Pack consecutive duplicates of list elements into sublists. ; If a list contains repeated elements they should be placed in separate sublists. (defn pack [l] (loop [output '() remaining l last-seen-list nil] (let [head (first remaining) tail (rest remaining) last-seen (first last-seen-list)] (if (nil? head) (reverse (cons last-seen-list output)) (if (= last-seen head) (recur output tail (cons head last-seen-list)) (recur (if (nil? last-seen-list) output (cons last-seen-list output)) tail (list head))))))) ; P10 (*) Run-length encoding of a list. ; Use the result of problem P09 to implement the so-called run-length encoding ; data compression method. Consecutive duplicates of elements are encoded as ; tuples (N, E) where N is the number of duplicates of the element E. (defn encode [l] (map (fn [a] (list (count a) (first a))) (pack l)))
Unlike my first pass in scala, I’m actually doing these as they’re intended. I’m using the results of P09 to implement P10. In my scala run, I wrote each one from scratch.