Why do I get these type errors?

Question

I have a data type:

data Tree = Empty | Node Int Tree Tree

and I want function

nodeDepth :: Tree -> [(Int, Int)] 

one pair for each node. The first element is label (value )and the second one is its depth.

My intention (raw code) is like :

nodeDepth (Node label left right) = zip nodeDepth' (Node label left right) [0]
nodeDepth' Empty _ = []
nodeDepth' (Node label left right) [level] = label : nodeDepth' (Node label left right) level : (1 + level)

But this does not work.

what's wrong? I am using Frege REPL

Error message are like :

E <console>.fr:22: t19906 occurs in type [t19906] rendering expression level{19727} untypable.

E <console>.fr:22: type error in  expression level
    type is   t19906
    used as   [t19906]

E <console>.fr:22: type error in  expression
    nodeDepth' (Node label left right) level:+ 1 level
    type is   [[t19909]]
    used as   [Int]


E <console>.fr:22: [[Int]] is not an instance of Num


E <console>.fr:20: type error in expression nodeDepth'
    type is apparently [t19961]
    used as function


H <console>.fr:20: too many or too few arguments perhaps?


E <console>.fr:20: type error in  expression Node label left right
    type is   Tree
    used as   [t19964]


E <console>.fr:20: type error in expression
    zip nodeDepth' (Node label left right)
    type is apparently [(t19961,t19964)]
    used as function


H <console>.fr:20: too many or too few arguments perhaps?


W <console>.fr:20: application of nodeDepth will diverge.

Answer 1

As for the errors consider the following line for instance:

nodeDepth (Node label left right) = zip nodeDepth' (Node label left right) [0]

since Haskell functional application associates to the left, zip takes the function nodeDepth' as its first parameter. To fix this particular error you might want to write:

zip (nodeDepth' (Node label left right)) [0]

But then you are still missing the second argument of nodeDepth', so the expression in the parenthesis just returns a function instead of a list.

Another mistake is when you define nodeDepth' for non-empty trees: your pattern matching [level] captures level as a single element and passes it to itself on the same line. This can be only resolved by assuming that level itself is a list, but that doesn't make too much sense either, since at the end of the line the addition assumes level to be of Numeric type.

nodeDepth' (Node label left right) [level] = label : nodeDepth' (Node label left right) level : (1 + level)

The following function nodeDepth iterates through the tree using depth-first search and constructs a list of the labels and the depths of the individual nodes.

data Tree = Empty | Node Int Tree Tree

wikiTree = Node 2 (Node 7 (Node 2 Empty Empty) (Node 6 (Node 5 Empty Empty) (Node 11 Empty Empty))) (Node 5 Empty (Node 9 (Node 4 Empty Empty) Empty))

nodeDepth :: Tree -> [(Int, Int)]
nodeDepth Empty = []
nodeDepth (Node label left right) = nodeDepthAccumulator (Node label left right) 0

nodeDepthAccumulator :: Tree -> Int -> [(Int, Int)]
nodeDepthAccumulator Empty _ = []
nodeDepthAccumulator (Node label left right) depth = (label,depth) : nodeDepthAccumulator left (depth+1) ++ nodeDepthAccumulator right (depth+1)

Executing nodeDepth on the example wikiTree you get:

> nodeDepth wikiTree
> [(2, 0),(7, 1),(2, 2),(6, 2),(5, 3),(11, 3),(5, 1),(9, 2),(4, 3)]

as you might have expected.

Answer 2

This:

zip nodeDepth' (Node label left right) [0]

The zip function expets two lists, but neither nodeDepth' nor (Node ...) are lists. And then you apply the result (which is a list), to some other list [0], this explains the second last message. I guess you meant to write

zip (nodeDepth' (Node label left right)) [0]

but even in this case there is an argument missing for nodeDepth' to make the expression in the parentheses a list.

The second definition for nodeDepth' is also not going to compile, for the following reasons:

• With the pattern [level] you match a one-element list, and call the single element level. Fine. But you use level as second argument to nodeDepth' (which is a list) and in the expression 1+level you use it as number.

• In an expression like

  a : b : c

c must be a list (it isn't in your example) and b must not be a list, and must have the same type as a. But nodeDepth' is supposed to return a list. Hence, the whole RHS makes no sense at all, therefore you get so many errors.

One tip here: since you obviously don't want level to be a list, and nowhere really pass a list to nodeDepth', wouldnt it be better to just replace the pattern [level] with level ?