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.