haskell depth tree

Question

I have got a tree and I need the depth of the tree, but it doesn't work.

data Tree a b = Leaf a | Branch (b,Tree a b) (b,Tree a b) deriving(Eq,Show)

tree = Branch ("A",Branch("C",Leaf 3)("D",Branch("G",Leaf 7)("H",Leaf 6)))("B",Branch("E",Leaf 5)("F",Leaf 4))

My function:

depth (d,Leaf x) = 1
depth (d,Branch a b) = 1 + (max (depth a) (depth b))

Couldn't match expected type `(t10, Tree t20 t10)'
with actual type `Tree Integer [Char]'
In the first argument of `depth', namely `tree'
In the expression: depth tree
In an equation for `it': it = depth tree

Is there any particular reason why you need pairs under your tree branches (that is, (b,Tree a b) rather than just (Tree a b))? — duplode
Use type signatures! Always. Here, that should pretty much solve the problem instantaneously. — leftaroundabout
I think your Branch is the essentially same as Branch b (Tree a b) (Tree a b): Branch (b,Tree a b) (b,Tree a b) ~= Branch b (Tree a b) b (Tree a b) ~= Branch (b, b) (Tree a b). If we have data NewTree = Leaf a | Branch b (Tree a b) (Tree a b), we can get the original tree with type OriginalTree a b = NewTree a (b, b). — David Young

duplode duplode · Accepted Answer · 2014-05-16T01:55:31

Your tree type:

data Tree a b = Leaf a | Branch (b,Tree a b) (b,Tree a b)

A Tree a b is either:

a Leaf containing an a value; or
a Branch containing two (b, Tree a b) pairs.

The patterns you write must follow that structure. You must match first Leaf or Branch and then whatever is inside them. So your depth should look like this:

depth :: Tree a b -> Int -- Always write signatures for your functions.
depth (Leaf x) = 1       -- There are no pairs anywhere in a Leaf.
depth (Branch (l1, t1) (l2, t2)) = 1 + max (depth t1) (depth t2)

The above can be made a little cleaner by noticing that, as we are not actually using the b "labels" and a "values", we can just ignore them. We do that with the _ pattern:

depth :: Tree a b -> Int
depth (Leaf _) = 1
depth (Branch (_, t1) (_, t2)) = 1 + max (depth t1) (depth t2)

haskell depth tree

2 Answers