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?

GS - Apologise to Monica GS - Apologise to Monica · Accepted Answer · 2014-09-20T09:52:06

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]

creating an instance for class TreeClass for datatype of an expression

1 Answers