Haskell - Обчислити рядок "let X = 3 in + X X" - haskell, recursion

Привіт Мені потрібна допомога при розрахунку типу. Вся програма передбачає взяти рядок, проаналізувати її, а в кінці - обчислити значення. Рядок, з якого я починаю, може бути таким: "let X = + 1 2 in * X 2 - X"Коли я проаналізую це, я отримаю це:"Let (Vari X) (Sum (Lit 1) (Lit 2)) (Mul (Vari X) (Lit 2)))". На даний момент я можу аналізувати такі вирази" * + 2 3 * 2 + 6 - 2 "і попередній, але я не можу розрахувати попереднє вираз"let X = + 1 2 in * X 2 - X"Якщо хтось може вказати мені в правильному напрямку, я був би щасливим, викликати зараз, я насправді не знаю, як я буду робити цю роботу. Дякую

Код:

data Chara = A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z deriving (Eq, Show)

data Number = Single Int | Many Int Number deriving (Eq, Show)

data Expr = Lit Int | Sub Expr | Sum Expr Expr | Mul Expr Expr | Vari Chara | Let Expr Expr Expr
deriving Show


--Want to calculate this
--Let (Vari X) (Sum (Lit 1) (Lit 2)) (Mul (Vari X) (Lit 2)))


calculate :: Expr -> Int
calculate (Sub a) = let e = calculate a in (-e)
calculate (Sum a b) = let e = calculate a
r = calculate b
in (e+r)
calculate (Mul a b) = let e = calculate a
r = calculate b
in (e*r)
calculate (Lit a) = a

Відповіді:

Вам доведеться виконати змінна заміна у вашому AST. І.е. вам потрібна функція

substitute :: (Chara, Expr) -> Expr -> Expr

який, враховуючи пару змінна для заміни і вираз замінити його буде перетнути дерево і виконати цю заміну. Це в основному означає: якщо ви знайдете a Vari, просто замінити його заміною. Якщо ви знайдете що-небудь з подразмерами, наприклад Sum a b, повторюється в ці субразракції, а потім перебудовує оператор з результатами, тобто

        Sum (substitute s a) (substitute s b)

Тоді calculate (Let var subst expr) = ... є досить простою закликом до substitute функція

Працює як чарівність

calculate :: Expr -> Int
calculate (Sub a) = let e = calculate a in (-e)
calculate (Sum a b) = let e = calculate a
r = calculate b
in (e+r)
calculate (Mul a b) = let e = calculate a
r = calculate b
in (e*r)
calculate (Let a b c) = calculate (substitute (getCharaFromExpr a) b c)
calculate (Lit a) = a


substitute :: Chara -> Expr -> Expr -> Expr
substitute x y (Lit a) = Lit a
substitute x y (Vari a) | x == a = y
| otherwise = Vari a
substitute x y (Sum a b) = Sum (substitute x y a) (substitute x y b)
substitute x y (Mul a b) = Mul (substitute x y a) (substitute x y b)
substitute x y (Sub a) = Sub (substitute x y a)
substitute x y (Let a b c) = Let (substitute x y a) (substitute x y b) (substitute x y c)