[Haskell-beginners] recursion and pattern matching

[Brent Yorgey]

Hi Alia,

On Tue, Oct 18, 2011 at 06:04:25AM -0700, Alia wrote:
> <snip Brent Yorgey's helpful advice>
> 
> I'm afraid my powers of abstraction are failing me, I managed to get the depth function ok
> 
> and along the way accidentally made a count (nodes) function:
> 
> 
> sumTree :: (Num b) => Tree a b -> b
> sumTree EmptyTree = 0
> sumTree (Node _ value children) = value + sum (map sumTree children)
> 
> count :: Tree a b -> Int
> count EmptyTree = 0
> count (Node _ value children) = 1 + sum (map count children) 
> 
> depth :: Tree a b -> Int
> depth EmptyTree = 0
> depth (Node _ value []) = 1
> depth (Node _ value children) = 1 + maximum (map depth children)

Great!  You could also make this a bit more modular by defining

  maximum0 [] = 0
  maximum0 xs = maximum xs

so that maximum0 handles the special case for the empty list of
children, then you could just get rid of the second case for depth and
use maximum0 in the last case.

> However, I'm stuck on the treeFold function given your function signature:
> 
> treeFold :: c -> (a -> b -> [c] -> c) -> Tree a b -> c
> 
> 
> At first I read it as c is an output type and also the type of the accumulator,
>  which addresses the EmptyTree scenario:
> 
> 
> treeFold acc f EmptyTree = acc

Yes, that's right.

> 
> So far so good. Now, the 2nd arg which is a function specification, takes
> an a and b (for the name and value respectively) and a list of cs.
> Now this is confusing to me because the value of b is actually desirable 
> as an output type as well. 

Yes, b *could* be desirable as an output type.  But that's OK, because
there is nothing stopping us from using the same type for both b and
c.  This way (using different type variables for b and c) someone can
use treeFold no matter whether they want the output type to be the
same or different than the type of the values.  It is perfectly
OK for different type variables to end up being the same type.  So
this version with both b and c is as general as possible.  If we made
b and c the same, treeFold would be less useful because there would be
some situations where you could not use it.

> Did you mean c to refer to a list of children.

Not quite. [c] refers to the list of *outputs* from calling treeFold
recursively on the children.

> If so then why didn't you write the func spec as:
> 
> treeFold :: b -> (a -> b -> [Tree a b] -> b) -> Tree a b -> b

This would not be a fold at all.  The point of a fold is that we
recursively fold any recursive substructures, and then say how to
combine the *outputs* from the folded substructures, not how to
combine the substructures themselves (which is what your type above
says).  Does that make sense?

> Sorry to be so dense about this, but I wanted to clarify this issue before I ran 
> off and started looking at Data.Monoid and Data.Foldable from Learn
> me a haskell (-:

You're not being dense, this stuff takes some getting used to. And
yes, making sure you understand this before going on to read about
Foldable is probably wise (although you shouldn't have any problems
with Monoid).

It's hard to know whether I am explaining something well over email.
Do my explanations above make sense, or are you still confused?

-Brent