read


read
or learn more

Transforming an accumulating mundane recursive fn into a tail-recursive fn (with Clojure)

Mar 8, 2011

this example is in Clojure, but the general principle stands regardless of language

Transforming an accumulating mundane recursive function to a tail-recursive function using a helper function.

(defn mundane-pack
  "Mundane recursive way to pack a sequence"
  [[f & r :as S]]
  (if (seq S)
    (let [[packed tail] (split-with {f true} S)]
      (if (seq tail)
        (cons packed (mundane-pack tail))
        [packed]))
    [nil]))

(defn pack
  "Tail-recursive way to pack a sequence"
  [coll]
  (letfn [(pack* [[f & r :as S] acc]
            (when (seq S)
              (let [[packed tail] (split-with {f true} S)]
                (if (seq tail)
                  (recur tail (conj acc packed))
                  (conj acc packed)))))]
    (pack* coll [])))

(defn rle 
  "Run-length encode a sequence"
  [coll]
  (map #(vector (count %) (first %))
       (pack coll)))

(def S '[a a a a b c c a a d e e e e])

(pack S)
;=> [(a a a a) (b) (c c) (a a) (d) (e e e e)]

(rle S)
;=> ([4 a] [1 b] [2 c] [2 a] [1 d] [4 e])

See Common Lisp: A Gentle Introduction to Symbolic Computation for more information about this technique.

:f

5 Comments, Comment or Ping

  1. You should also mention the third option to rewrite list-accumulating mundane recursive fns in Clojure: laziness. lazy-pack is (partial partition-by identity) but implemented this way it obviously misses the point of the exercise.

  2. @cgrand

    Indeed. I had another post in me that would cover that very ground, but maybe your comment will suffice. :-)

  3. Forgive me if I’m misunderstanding things, but should the symbol pack be mundane-pack in the first function?

  4. @Sam

    You are absolutely correct. Thanks.

  5. Paul

    A good technique to know. I would have used loop instead of leftn. For some reason I never seem to use the latter.

Reply to “Transforming an accumulating mundane recursive fn into a tail-recursive fn (with Clojure)”