CODEWITHSUNDEEP
haskelltreealgebraic-data-types
shashydhar
shashydhar

Reputation: 811

algebraic data type for tree

I'm trying to build a tree where its children are represented in a list. Each of the children may themselves be subtrees etc. So I go this way --

data Children a = NoChildren | Cons a (Children a) deriving (Show, Read, Ord, Eq)
data Tree a = EmptyTree | Node a (Children a) deriving (Show, Read, Ord, Eq)

now i try to create a tree like this 

let subtree1 = Node 67 NoChildren
let subtree2 = Node 86 NoChildren
let tree1 = Node 83 (subtree1 `Cons` (subtree2 `Cons` NoChildren))

it works fine till subtree2. tree1 is not created. The error thrown is this -

<interactive>:96:15:
    No instance for (Num (Tree Integer))
      arising from the literal `83'
    Possible fix: add an instance declaration for (Num (Tree Integer))
    In the first argument of `Node', namely `83'
    In the expression: Node 81 (subtree1 `Cons` (subtree2 `Cons` NoChildren))
    In an equation for `tree1':
      tree1 = Node 81 (subtree1 `Cons` (subtree2 `Cons` NoChildren))

I don't understand this error error at all. Why is it complaining that 83 is a literal. subtree1 and subtree2 had literals too and they were fine...

I solved the problem by doing the following

data Tree a = EmptyTree | Node a [Tree a] deriving (Show, Read, Ord, Eq)

flatten [] = []
flatten x:xs = x ++ flatten xs

preorder EmptyTree = []
preorder (Node a []) = [a]
preorder (Node a children) = [a] ++ flatten (map preorder children)

Upvotes: 0

Views: 349

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183888

data Children a = NoChildren | Cons a (Children a)

means your Children a is isomorphic to [a], and hence your

data Tree a = EmptyTree | Node a (Children a)

is isomorphic to

data List a = Empty | Nonempty a [a]

which is again isomorphic to [a].

What you want is that the children themselves are Trees, so you should use

data Children a = NoChildren | Cons (Tree a) (Children a)

or plain

data Tree a = EmptyTree | Node a [Tree a]

The error is because subtree1 has type Tree a for some a belonging to Num (ditto for subtree2). Then when you write

tree1 = Node 83 (subtree1 `Cons` (subtree2 `Cons` NoChildren))

the inferred type of tree1 is Tree (Tree a) (for some a belonging to Num), and hence

83 :: Tree a

But there's no Num instance for Trees.

Upvotes: 4

Related Questions