title: Can Strictness Guide Recursion?
body: <p>Let's say we have a simple tree creating algorithm in Haskell:</p>
  
  <pre><code>data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)
  
  makeTree :: Tree Int -&gt; 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
  </code></pre>
  
  <p>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?</p>
  
  <p>EDIT:</p>
  
  <p>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:</p>
  
  <pre><code>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 (:[])
  </code></pre>
  
  <p>The flattening of the tree is thus invoked and it is <em>probably</em> 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?</p>