CODEWITHSUNDEEP
haskell
user3642985
user3642985

Reputation: 11

haskell depth tree

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

Upvotes: 0

Views: 1490

Answers (2)

duplode
duplode

Reputation: 34398

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)

Upvotes: 5

Anschel Schaffer-Cohen
Anschel Schaffer-Cohen

Reputation: 911

The depth function, as you've written it, seems to take a pair as its argument: (d, Leaf x) for example. But you then tried to call it with just a tree. What is d?

Upvotes: 2

Related Questions