Can Strictness Guide Recursion?

Question

Let's say we have a simple tree creating algorithm in Haskell:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) makeTree :: Tree Int -> Tree Int makeTree (Node 0 l r) = Node 0 EmptyTree EmptyTree makeTree (Node n l r) = Node n (makeTree $ newTree (n - 1)) (makeTree $ newTree (n - 1)) where newTree n = Node n EmptyTree EmptyTree

For extremely large numbers, we would expect this algorithm to fail with a "stack size overflow" error. This would be because the algorithm is binary recursive, not tail recursive. Can I use bang patterns (on the resulting left subtree "!(makeTree $ newTree (n - 1))") to guide the binary recursion into tail recursion, as the recursion should now be directed due to strictness?

EDIT:

It turns out that the real issue is not the creation of the tree, but the functions that consume the tree. There is another function used to flatten the tree, where the instance is as follows:

import qualified Data.Foldable as F instance F.Foldable Tree where foldMap f EmptyTree = mempty foldMap f (Node x l r) = F.foldMap f l `mappend` f x `mappend` F.foldMap f r flatten = F.foldMap (:[])

The flattening of the tree is thus invoked and it is probably here where the overflow occurs. If so, is the solution as simple as hypothetically the conversion of foldl to foldl'? Or is the binary folding going to add additional problems?

Huh? Even if this was strict, these recursions can't be tail because a tail call must be the last thing a function does. Here you also call the Node constructor after your called both recursions. — tohava
– tohava, Commented Jul 28, 2013 at 15:23
If you fix the code so it compiles, there will be no stack overflow from this function. Laziness helps... — augustss
– augustss, Commented Jul 28, 2013 at 15:49
I was just using ghci for a quick correct function, I'm assuming I just need a main for the code to compile. — user1104160
– user1104160, Commented Jul 28, 2013 at 19:03

Petr · Accepted Answer · 2013-07-28 15:54:51Z

I assume that you meant to create a very deep tree, like

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) makeTree :: Int -> Tree Int makeTree 0 = EmptyTree makeTree n = Node n (makeTree (n - 1)) (makeTree (n - 1))

The key is that Haskell is lazy. So after calling the function, nothing is actually created, except a thunk that is evaluated when needed. Nothing is allocated on stack, because the call to makeTree doesn't involve a recursive call. After the root node is examined, the recursive calls are invoked, but again only one level. This means that examining each node costs only some finite time and memory (in this case constant), not depending on the depth of the tree. The important property is that every recursive call is inside a constructor. This is sometimes called corecursion or guarded recursion.

It's possible a stack overflow will occur in a function that consumes the tree, but this is a different matter.

Interesting, I guess I made the silly assumption that the creation of the tree was the issue. Then yes, I do consume the tree later (I flatten the tree). That instance of a foldable tree is in the edited question. Why would the thunks appear for the folding and not the tree creation, though (if this actually happens)? What makes this foldMap instance different?
@user1104160 Imagine Haskell's data like mathematical objects. When you "create" them, they don't exists. They are only dormant in thunks, just like mathematical objects are in our imagination. Due to laziness, Haskell starts creating them only when they're needed.
So what you're saying is that I shouldn't get a stack size overflow with flattening that tree, as it traverses the entire tree just as creating the tree does, so the same amount of "only when needed" is executed?
@user1104160 I'd say it depends on the depth of your tree. You could get an stack overflow exception if the tree is really deep. Could you post a self-contained piece of code that results in an exception?

Collectives™ on Stack Overflow

Can Strictness Guide Recursion?

1 Answer 1

5 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Related