Hi Alia, On Tue, Oct 18, 2011 at 06:04:25AM -0700, Alia wrote:
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