[Haskell-beginners] recursion and pattern matching

[Alia]

Sorry, as soon as I sent my email below, I realized that c should remain arbitrary because we don't
yet know whatwe want (if the function is to be truly pluggable) so you were probably right in your 

initial signature (I think).

so:


treeFold :: c -> (a -> b -> [c] -> c) -> Tree a b -> c


c is the target accumulator and the following still holds:

treeFold acc f EmptyTree = acc
But then unless we apply some function that recurses into the
tree and generates [c] shouldn't the signature of f be:

f :: (a -> b -> [Tree a b] -> c)


so that:

treeFold :: c -> (a -> b -> [Tree a b] -> c) -> Tree a b -> c

where we use the inital c as the accumulator and our
function folds the tree into the intermediate c values to 

ultimately reduce to the output c..

or am I completely off?

AK



----- Original Message -----
From: Alia <alia_khouri at yahoo.com>
To: "beginners at haskell.org" <beginners at haskell.org>
Cc: 
Sent: Tuesday, October 18, 2011 4:04 PM
Subject: re: [Haskell-beginners] recursion and pattern matching 

<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)


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

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. Did you mean c to refer to a list of 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
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 (-:


AK