title: Where do the foldl/foldr implementations of Foldable come from for binary trees in haskell?
body: <p>I'm working through Learn You a Haskell, and I'm on the section on monoids. In this section, the author defines the foldMap method for a tree as follows:</p>
  
  <pre><code>instance F.Foldable Tree where  
      foldMap f Empty = mempty  
      foldMap f (Node x l r) = F.foldMap f l `mappend`  
                               f x           `mappend`  
                               F.foldMap f r  
  </code></pre>
  
  <p>Which works fine and is totally baller. However, he then states "Now that we have a Foldable instance for our tree type, we get foldr and foldl for free!" and shows the following code:</p>
  
  <pre><code>testTree = Node 5  
              (Node 3  
                  (Node 1 Empty Empty)  
                  (Node 6 Empty Empty)  
              )  
              (Node 9  
                  (Node 8 Empty Empty)  
                  (Node 10 Empty Empty)  
              )  
  
  ghci&gt; F.foldl (+) 0 testTree  
  42  
  ghci&gt; F.foldl (*) 1 testTree  
  64800  
  </code></pre>
  
  <p>Now I'm confused. Nowhere was an implementation for foldl or foldr written for Trees. The functions seem to work sort of like the foldmap, but putting the initial accumulator as the head of the tree, and then foldMapping over the appropriate monoid, but it can't actually be working like this because foldl and foldr take more general functions than the monoids '+' and '*' as arguments. Where are foldl and foldr actually implemented, how do they work, and why does defining foldMap cause them to exist?</p>