{"id":250,"date":"2006-12-20T14:02:57","date_gmt":"2006-12-20T14:02:57","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2006\/12\/20\/tail-recursion-iteration-in-haskell\/"},"modified":"2006-12-20T14:02:57","modified_gmt":"2006-12-20T14:02:57","slug":"tail-recursion-iteration-in-haskell","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2006\/12\/20\/tail-recursion-iteration-in-haskell\/","title":{"rendered":"Tail Recursion: Iteration in Haskell"},"content":{"rendered":"

In Haskell, there are no looping constructs. Instead, there are two alternatives: there are list iteration constructs (like foldl<\/code> which we’ve seen before), and tail recursion<\/em>. Let me say, up front, that in Haskell if you find yourself writing any iteration code on a list or tree-like structure, you should always look in the libraries; odds are, there’s some generic function in there that can be adapted for your use. But there are always cases where you need to write something like a loop for yourself, and tail recursion is the way to do it in Haskell.<\/p>\n

Tail recursion is a kind of recursion where the recursive call is the very last<\/em>
\nthing in the computation of the function. The value of tail recursion is that in a tail
\nrecursive call, the caller does nothing except pass up the value that’s returned
\nby the the callee; and that, in turn, means that you don’t need to return to the caller
\nat all<\/em>! If you think of it in terms of primitive machine-level code, in a tail-recursive call, you can use a direct branch instruction instead of a branch-to-subroutine; the tail-recursive call does *not* need to create a new stack frame. It can just reuse the callers frame. <\/p>\n

<\/p>\n

Let’s look at one quick example. Suppose you’ve got a list of integers, and you’d like to
\ntake the sum. If you were writing that in an imperative language like C, you’d write
\nsomething like:<\/p>\n

\nint sum(int len, int *array) {\nint sum=0;\nint i;\nfor (i=0; i < len; i++) {\nsum += array[i];\n}\nreturn sum;\n}\n<\/pre>\n
 What’s nice about that code is that it doesn’t use any stack space for the
\niteration. You can call it for an array of essentially any size, and it use the same
\namount of memory to produce the sum. The naive way of writing that in Haskell (assuming we were being stupid and not using any of the library functions like `foldr`) would be
\nsomething like:<\/p>\n
\n>naiveSumList :: [Integer] -> Integer\n>naiveSumList (x:xs) = x + (naiveSumList xs)\n>naiveSumList [] = 0\n<\/pre>\n
 The problem with implementing it that way is that it’s very wasteful of space. It ends up
\nusing **O**(n) space in the length of the list! That’s because for each element of the list,
\nthere is a recursive call to the function which allocates a new stack frame. To illustrate this, consider the two following diagrams: one is a stack diagram, where the vertical line
\nrepresents the lifetime of the stack frame, and new frames appear to the right of their parents; the other is a lambda-calculus expansion showing how a pure syntactic expansion
\nwould evaluate.<\/p>\n
\"Non-tail<\/p>\n
\nnaiveSumList [3, 4, 5, 6] =>\n3 + (naiveSumList [4,5,6] =>\n3 + (4 + naiveSumList [5,6])) =>\n3 + (4 + (5 + (naiveSumList [6]))) =>\n3 + (4 + (5 + (6 + (naiveSumList [])))) =>\n3 + (4 + (5 + (6 + 0))) =>\n3 + (4 + (5 + 6)) =>\n3 + (4 + 11) =>\n3 + 15 =>\n18\n<\/pre>\n
 As you can see, the stack frame of each call needs to survive longer<\/em> than the frame of any functions that it calls – because each call to naiveSumList<\/code> for a non-empty list needs to get the return value of the recursive call, and add it to its x<\/code> parameter before it can return. All of the stack frames need to be preserved – because an action needs to be performed in the context of each
\nframe before that frame can be dropped.<\/p>\n
 In a tail-recursive function, the stack frames do not<\/em> need to be preserved. There is no action that needs to be taken in the context of a frame after<\/em> it makes its
\nrecursive call. So instead of creating a stack frame for each member of the list, it can
\ncreate one<\/em> stack frame, and just reuse it.<\/p>\n
 So, let’s look at a tail recursive addition loop in Haskell. <\/p>\n
\n>sumList :: [Integer] -> Integer\n>sumList lst = sumLoop lst 0 where\n>    sumLoop (x:xs) i = sumLoop xs (i+x)\n>    sumLoop [] i = i\n<\/pre>\n
 Now, let’s look at the corresponding diagrams for the tail-recursive version. The only frame that needs to be kept is the frame for the initial call to sumList<\/code>; it calls sumLoop<\/code>, which can reuse the same stack frame – which calls itself recursively, reusing the same stack frame; and when it’s
\ndone with the list, sumLoop<\/code> can return its result directly to the caller of sumList.<\/p>\n
\"Non-tail<\/p>\n
\nsumList [3,4,5,6] =>\nsumLoop [3,4,5,6] 0 =>\nsumLoop [4,5,6] 3 =>\nsumLoop [5,6] 7\nsumLoop [6] 12 =>\nsumLoop [] 18 =>\n18\n<\/pre>\n
 The trick that I used to create the tail-recursive version is a very common technique for creating a tail-recursive loop. What would be loop index variables\/accumulator variables in an imperative language become parameters<\/em> in the tail-recursive version. So instead of the line of C code that initializes the accumulator sum<\/code> to 0, in the Haskell version, sumList<\/code> calls sumLoop<\/code> with an initial parameter value of 0. Instead of adding the next list element to the accumulator, we pass the sum as a parameter to the next iteration. <\/p>\n
 How about our binary tree example? Binary tree search is already<\/em> tail recursive.
\nSearching checks the value in the current node, and either returns immediately, or returns the
\nvalue of calling search on a subtree. What if we wanted to do insert<\/em> in a tail
\nrecursive way? In the typical implementation, you call insert on a subtree, and then return a new tree node that includes the value of the subtree node: so there's something that needs to
\nbe done after<\/em> the recursive call returns, which means that the stack frame needs to be kept? We can<\/em> do it. It's pretty pointless: realistically, we probably wouldn't want to bother doing it tail recursively, because the stack for recursively working down a binary tree will never get that deep, and the information that we need to pass as parameters will be as large as the set of stack frames. But it makes a nice explanatory example, so we'll do it anyway.)<\/p>\n
 The trick in converting to tail recursion is to capture whatever information is needed
\nto generate the result into a parameter that's passed along with the function. For a tree
\ninsert, we need to find the correct place to insert the new value, and then we need to
\npatch that insertion into the path of nodes up the tree to the root. So what we need to
\npass down the recursive calls is the path taken down the tree in the course of searching
\nfor an insertion location.<\/p>\n
 That description that I just wrote is pretty clearly a two-phase thing: search for the
\ninsertion location; and then patch the tree. Anytime you see a description like that, it's a
\ngood clue that you probably want to write it as separate functions. We'll split it into
\nfindInsertPath<\/code>, which searches down the tree, finding the insert location and
\ngenerating a list containing the from the insertion point back to the tree root; and
\npatchTree<\/code>, which takes a new node for a newly inserted value, and follows the
\npath created by findInsertPath<\/code> back up the tree creating the parent nodes for the
\nnew tree with the inserted value. Since the only time we're going to call
\npatchTree<\/code> or findInsertPath<\/code> is inside of ttInsert<\/code>,
\nwe'll make them local functions  using a where<\/code> clause.<\/p>\n
\n>data (Ord a) => TailTree a = TTNode a (TailTree a) (TailTree a)\n>                | TTEmpty deriving (Show)\n>\n>ttInsert :: (Ord a) => a -> TailTree a -> TailTree a\n>ttInsert newval tree =\n>    patchPath (TTNode newval TTEmpty TTEmpty) (findInsertPath newval tree []) where\n>         findInsertPath newval node@(TTNode v left right) path\n>               | v > newval = findInsertPath newval left (node:path)\n>               | otherwise = findInsertPath newval right (node:path)\n>         findInsertPath newval TTEmpty path = path\n>         patchPath node [] = node\n>         patchPath node@(TTNode a _ _) ((TTNode v left right):path)\n>               | v > a = patchPath (TTNode v node right) path\n>               | otherwise = patchPath (TTNode v left node) path\n<\/pre>\n
 When you're not used to it, that looks pretty weird. But if you take the time to look
\nthrough it carefully, it's reasonably easy to follow. The downward half, when
\nfindInsertPath<\/code> is walking down the tree should be easy to understand. The second
\nstage, when patchPath<\/code> is walking back up the tree looks a bit odd, but if you
\ntrace it out on paper you'll see that it's doing exactly the same thing, in exactly the same
\norder as the return path of a the regular non-tail-recursive version. The only real difference
\nis that instead of letting the call stack maintain the list of nodes that need to be rebuilt
\nfor the post-insert tree, and then guide the way through rebuilding the tree, we've taken that and made it explicit in the code, doing everything with tail calls.<\/p>\n
Let's trace it, just to see. To make it easier to read, I'm going to use a more compact non-Haskell syntax for the trees. For empty nodes, I'll just leave their values empty,
\nand for non-empty nodes, I'll write {val:left\/right}. Let's start with a tree:<\/p>\n
\n{10:{5:{3:\/}\/{7:\/}\/{16:{14:{12:\/}\/}\/{18:{17:\/}\/{21:{19:\/}\/}}}}}\n<\/pre>\n
Drawn in tree form, that's:<\/p>\n
\"sample<\/p>\n
 To make things easier, I'll also abbreviate tree nodes sometimes. To reproduce a subtree that appeared before, I'll just write {val:...}. So, for example, I might
\nabbreviate the tree above as {10:{5:...}\/{16:...}}. Lets walk through
\nthe evaluation of ttInsert<\/code> to add the value 15<\/code> to thee xample tree above.<\/p>\n
\nttInsert 15 {10:{5:{3:\/}\/{7:\/}\/{16:{14:{12:\/}\/}\/{18:{17:\/}\/{21:{19:\/}\/}}}}} =>\npatchPath {15:\/} (findInsertPath 15 {10:{5:...}\/{16:...}} []) =>\nfindInsertPath 15 {10:{5:...}\/{16:...}} [] =>\nfindInsertPath 15 {16:{14:...}\/{18:...}} [{10:...}] =>\nfindInsertPath 15 {14:{12:\/}\/} [{16:...},{10:...}] =>\nfindInsertPath 15 {} [{14:...},{16:...},{10:...}] =>\npatchPath {15:\/} [{14:...},{16:...},{10:...}] =>\npatchPath {14:{12:\/}\/{15:\/}} [{16:...},{10:...}] =>\npatchPath {16:{14:{12:\/}\/{15:\/}}\/{18:...}} [{10:...}] =>\npatchPath {10:{5:...}\/{16:{14:{12:\/}\/{15:\/}}\/{18:...}} [] =>\n{10:{5:{3:\/}\/{7:\/}}{16:{14:{12:\/}\/{15:\/}}\/{18:\/{17:\/}\/{21:{19:\/}\/}}}}\n<\/pre>\n<\/p>\n
If you look at the tree parameter in each call of patchPath,
\nit's precisely the return value of the corresponding recursive call
\nto insert in the non-tail recursive version. (In the first draft of this,
\nI screwed up in the third call to findInsertPath<\/code>. Thanks to Craig Fratrik
\nfor pointing out the error.)<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
In Haskell, there are no looping constructs. Instead, there are two alternatives: there are list iteration constructs (like foldl which we’ve seen before), and tail recursion. Let me say, up front, that in Haskell if you find yourself writing any iteration code on a list or tree-like structure, you should always look in the libraries; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[89],"tags":[],"class_list":["post-250","post","type-post","status-publish","format-standard","hentry","category-haskell"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-42","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/250","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=250"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/250\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=250"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=250"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}