Transforming an accumulating mundane recursive fn into a tail-recursive fn (with Clojure)
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
cgrand
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.
Mar 9th, 2011
fogus
@cgrand
Indeed. I had another post in me that would cover that very ground, but maybe your comment will suffice. :-)
Mar 9th, 2011
Sam Aaron
Forgive me if I’m misunderstanding things, but should the symbol
packbemundane-packin the first function?Mar 9th, 2011
fogus
@Sam
You are absolutely correct. Thanks.
Mar 9th, 2011
Paul
A good technique to know. I would have used loop instead of leftn. For some reason I never seem to use the latter.
Mar 9th, 2011
Reply to “Transforming an accumulating mundane recursive fn into a tail-recursive fn (with Clojure)”