Fatvat

So, onwards with spending a few minutes each day working my way through a random list of puzzles...

P08 - Eliminate consecutive duplicates of list elements

;; Ugly style
(defn eliminate-dupes [lst]
 ((fn [n last accum]
    (if (= nil n)
      accum
      (if (= (first n) last)
        (recur (rest n) last accum)
        (recur (rest n) (first n) (concat accum (list (first n))))))) lst nil '()))

;; Nicer functional style
(defn eliminate-dupes2 [lst]
 ((fn [n accum]
    (if (= nil n)
      accum
      (recur (drop-while (fn [x] (= x (first n))) n) 
      (concat accum (list (first n)))))) lst nil))

drop-while and take-while are functions that read from a (potentially) infinite sequence and either take or drop elements based on a predicate. They are (obviously) lazily evaluated!

P09 - Pack consecutive duplicates of list elements into sublists

;; P09 - pack consecutive duplicates of list elements into sublists
;; TODO should really use an accumulator
(defn pack-list [lst]
  (if (= lst nil)
    nil
    (cons (take-while (fn [x] (= x (first lst))) lst) 
   (pack-list (drop-while (fn [x] (= x (first lst))) lst)))))

(defn pack-list2 [lst]
  ((fn [xs accum]
     (if (= xs nil)
       accum
       (recur (drop-while (fn [x] (= x (first xs))) xs) 
       (concat accum (list (take-while (fn [x] (= x (first xs))) xs)))))) lst nil))

The transformation from non tail recursive, to tail recursive + accumulator is very formulaic. A quick search led me to LtU and in turn to LLVM.

LLVM is a low level virtual machine (doesn't provide GC / type system etc). It provides a framework for allowing optimizations to be generated and amongst these are including tail call optimization and transform. See the demo. Unfortunately, until it's possible to guarantee that this optimization is performed, you have to assume the worst and right code with explicit accumulators. Ho-hum!

P10 - Run length encoding of sublists

(defn encode [lst]
  ((fn [xs accum]
     (if (= nil xs)
       accum
       (recur (rest xs) (concat accum (list (list (count (first xs)) (ffirst xs))))))) (pack-list lst) nil))

count was a difficult one to find - it returns the length of a sequence, also works on strings, arrays and Java collections.

doc is an amazingly useful function that returns the documentation string associated with a function e.g.

user> (doc count)
-------------------------
clojure.core/count
([coll])
  Returns the number of items in the collection. (count nil) returns
  0.  Also works on strings, arrays, and Java Collections and Maps
nil

Labels: clojure