создания экземпляра класса для TreeClass для типа данных выражения

Question

Если у меня есть 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 

Я создал класс TreeClass где поддеревьев :: гр -> [т]

я создал экземпляр класса для типа данных MTree данных MTree а = MTree а [MTree а] получения Показать

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

singleton a = MTree a [] 

нет w Я хотел бы сделать то же самое для типа данных Expr. У меня есть выражения типа уравнение для ex1 is ex1 = y + x * 11/100 это должно быть сделано в дерево и рассчитать высоту и различные параметры, такие как количество узлов , листы и т.д.

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

Выражение - это дерево. Я попытался написать функцию поддерева Expr типа данных следующего

instance TreeClass Expr where 
subtrees a = a 

вычислить высоту функции дерева высоты записываются как

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 

Но при выполнении его на GHCI (высота EX1) он вводит бесконечный цикл. Я знаю, что неправильно написано выражение subTree для выражения типа Expr.

Как выполнить высоту ex1?

Answer 1

Вы говорите, что a является его поддеревом, поэтому height заканчивается бесконечным циклом, когда он пытается вычислить высоту поддеревьев.

Вам необходимо написать поддеревья по анализу case на разных конструкторах Expr. Например, в случае ExprAdd будет:

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