creating an instance for class TreeClass for datatype of an expression

Question

If I have a dataytype Expr

data Expr = ExprNum Double -- constants
          | ExprVar String -- variables
          | ExprAdd Expr Expr
          | ExprSub Expr Expr
          | ExprNeg Expr -- The unary '-' operator
          | ExprMul Expr Expr
          | ExprDiv Expr Expr
          deriving Show

I have created a class TreeClass where subTrees :: t -> [t]

I created an instance of the class for the datatype MTree data MTree a = MTree a [MTree a] deriving Show

instance TreeClass (MTree a) where
subtrees (MTree _ ss) = ss

singleton a = MTree a []

Now I wish to do The same for Expr datatype .I have expressions like the equation for ex1 is ex1 = y + x * 11 / 100 this has to be made into a tree and calculate the height and various parameters like number of nodes,leafs etc.

ex1 = ExprAdd (ExprVar "y")(ExprMul (ExprVar "x")(ExprDiv (ExprNum 11) (ExprNum 100)))

The expression is a Tree. I tried to write the subTree function for Expr datatype as follows

instance TreeClass Expr where
subtrees a  = a

to calculate the height of the tree height function is written as

height :: (TreeClass t) => t -> Int
height t = 1 + foldl (\x y -> max x (height y)) 0 (subtrees t)

numNodes :: (TreeClass t) => t -> Int
numNodes t = 1 + foldl (\x y -> x + numNodes y) 0 (subtrees t)

leafs :: (TreeClass t) => t -> [t]
leafs t = case subtrees t of
  [] -> [t]
  st -> foldl (\x y -> x ++ leafs y) [] st

But while executing it on ghci (height ex1) its entering an infinite loop. I know I am going wrong in writing subTree Expression for Expr datatype.

How do I execute height ex1?

Ganesh Sittampalam · Accepted Answer · 2014-09-20 09:52:06Z

2

You're saying that a is a subtree of itself, so height ends up in an infinite loop when it tries to calculate the height of the subtrees.

You need to write subtrees by case analysis on the different constructors of Expr. For example, the case for ExprAdd would be:

subtrees (ExprAdd e1 e2) = [e1, e2]

answered Sep 20, 2014 at 9:52

Ganesh Sittampalam

29.1k4 gold badges82 silver badges102 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

anujuhi01 Over a year ago

I tried this way but its saying non- Exhaustive patter.It is not getting any terminating condition.

Ganesh Sittampalam Over a year ago

That line was just an example, you need to add a separate line for each constructor of Expr.

anujuhi01 Over a year ago

subtrees (ExprMul a b) = [a,b] subtrees (ExprAdd a b) = [a,b] subtrees (ExprDiv a b) =[a,b] subtrees (ExprSub a b) = [a,b] I got that..and I did this and even for ExprVar and ExprNum

Ganesh Sittampalam Over a year ago

Remember to include cases for the constructors that don't have any subtrees either, e.g. subtrees (ExprVar _) = []. If you look at the "non-exhaustive pattern" error it'll tell you what you've omitted.

anujuhi01 Over a year ago

The error is Non-exhaustive patterns in function subtrees

|

Collectives™ on Stack Overflow

creating an instance for class TreeClass for datatype of an expression

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related