Today, I’ll take you on a another little walk through the land of program transformations. Let’s begin with a simple binary tree, with value of unknown type in the leaves, as well as the canonical
data T a = L a | B (T a) (T a)
map1 :: (a -> b) -> T a -> T b map1 f (L x) = L (f x) map1 f (B t1 t2) = B (map1 f t1) (map1 f t2)
As you can see, this
mapfunction is using the program stack as it traverses the tree. Our goal is now to come up with a
mapfunction that does not use the stack!
Why? Good question! In Haskell, there wouldn’t be a strong need for this, as the Haskell stack is allocated on the heap, just like your normal data, so there is plenty of stack space. But in other languages or environments, the stack space may have a hard limit, and it may be advised to not use unbounded stack space.
That aside, it’s a fun exercise, and that’s sufficient reason for me.
(In the following, I assume that tail-calls, i.e. those where a function end with another function call, but without modifying its result, do not actually use stack space. Once all recursive function calls are tail calls, the code is equivalent to an imperative loop, as we will see.)