Vfrdtyky

I want to calculate the maximum degree in a Tree which has an arbitrary number of branches.

data Tree a = Node a [Tree a]

  deriving (Eq, Show)



{-



       2

    /  |  

   7   3   1

       |  / 

       0 3   2

 For this case: Answer will be 3. 

-}

tree1 :: Tree Int

tree1 = Node 2 [Node 7 , Node 3 [Node 0 ], Node 1 [Node 3 , Node 2 ]]



--I am doing something like this:



maxBranching :: Tree Int -> Int

maxBranching Node n  = 1

maxBranching Node n xs = max (length xs) maxBranching xs

Now, I am getting an error. How can I write the correct pattern to solve this problem?

Firstly, the type of parameter of maxBranching is Tree Int and not [Tree Int] and you want to map all Children Nodes to its maximum degrees, so it should be:

map maxBranching xs

Not

maxBranching xs

Secondly, parameter need in parentheses, otherwise, the function maxBranching become accept 3 parameters.

put them all as:

maxBranching :: Tree Int -> Int

maxBranching (Node _ ) = 1

maxBranching (Node _ xs) =  maximum $ (length xs) : (map maxBranching xs)

You want to traverse a tree generating a sort of "summary value". This is a classic example of a catamorphism or fold. The general fold for trees looks like this:

foldTree :: (a -> [b] -> b) -> Tree a -> b

foldTree f (Node a bs) = f a (map (foldTree f) bs)

The idea here is that at each tree node,

Node r [t1,t2,t3]

we first reduce each child recursively to a summary value, then apply the given function and the root value and the summaries of the children to produce a summary for the tree.

Now

maxBranching :: Tree a -> Int

maxBranching = foldTree $

  _ bs -> maximum (length bs : bs)

That is, at each node, we take the maximum of the number of branches of that node and each of its children.

First of all, you need to put parentheses around your argument, like this:

maxBranching (Node n xs) = ...

If you don't put parentheses around your arguments, the compiler can't know if n and xs/ belongs to Node or maxBranching.

Next issue you have is that your recursive call is done on a list of Tree Int instead of just a Tree Int. What you need to do is to get the maxBranching of each subtree and then compare the result to each other. So a first, naive approach, would be the following:

maxBranching (Node n xs) = max (length xs) (maximum (map maxBranching xs))

map will run maxBranching on every element of the list xs, returning an array of Int. maximum will then take the max in the list. The difference between max and maximum is that max only takes two arguments and compare them, while maximum takes a list which is arbitrarily long.

We could get rid of maxby adding length xs into the list we created, and running maximum on everything, like this:

maxBranching (Node n xs) = maximum $ (length xs):(map maxBranching xs)

And if you don't know, $ is equvivalent with putting parantheses around the rest of the line (more or less).

You could also use smart methods as folding and the like, but I just wanted you to understand the errors you did and how to fix them without changing the core idea of your solution.