Сначала: я знаю достаточно мало о Haskell, и мое общее время, потраченное на программирование языка, составляет не более 8 часов в течение 5 лет или около того, хотя я много читал об этом языке. Таким образом, простите, без сомнения, ужасный стиль.
Я решил эту проблему, так как это выглядело как простой способ немного разобраться в программировании на Haskell. Сначала я создал тип данных, вдохновленный примером:
data Expr = Const Int | Mult Expr Expr | Plus Expr Expr | Var String
Я сделал это немного проще, чем оригинал, и пропустил минус, но в остальном все так же.
Я быстро обнаружил, что значения построены с использованием, например, «Const 4» не был напечатан с вышеупомянутым, поскольку не было никакой применимой функции показа. Я сделал Expr экземпляром класса Show type и предоставил простое определение show с учетом приоритета оператора:
instance Show Expr where
show (Const n) = show n
show (Var n) = show n
show (Plus a b) = (show a) ++ "+" ++ (show b)
show (Mult a b) = "(" ++ (show a) ++ ") * (" ++ (show b) ++ ")"
Следующей была сама задача по упрощению. Как подсказывает Гломек, существует проблема с попыткой оценить все, просто используя сопоставление с образцом в одной функции.
В частности, для любой данной операции (все операции в примере являются двоичными) вы хотели бы сначала упростить левое дерево, затем правое дерево, а затем упростить текущий Expr на основе того, что оценивали эти поддеревья; например если оба упрощены до Const, то вы можете заменить все поддерево оцененной операцией. Однако сопоставление с образцом заставляет вас выбирать, что делать, основываясь на дочерних узлах непосредственного узла, а не на том, что поддеревья возвращают после упрощения.
Таким образом, чтобы получить сопоставление с образцом, чтобы решить, оценивать ли текущий узел или нет как постоянное подвыражение, важно упростить поддеревья, а затем выполнить диспетчеризацию на основе упрощенного целого.
Я сделал это, используя отдельную функцию, которую я назвал eval, целью которой является сопоставление с образцом в вещах, которые можно уменьшить, предполагая, что поддеревья уже были уменьшены. Он также обрабатывает умножение на 0 и 1 и добавление 0:
-- Tries to evaluate any constant expressions.
eval :: Expr -> Expr
eval (Mult (Const a) (Const b)) = Const (a * b)
eval (Mult (Const a) b)
| a == 0 = Const 0
| a == 1 = b
| otherwise = (Mult (Const a) b)
eval (Mult a (Const b))
| b == 0 = Const 0
| b == 1 = a
| otherwise = (Mult a (Const b))
eval (Plus (Const a) (Const b)) = Const (a + b)
eval (Plus (Const a) b)
| a == 0 = b
| otherwise = (Plus (Const a) b)
eval (Plus a (Const b))
| b == 0 = a
| otherwise = (Plus a (Const b))
eval e = e
Теперь, когда у меня есть eval, и я знаю, что безопасно вызывать на верхнем уровне дерева выражений (т. Е. Он не будет бесконечно повторяться), я могу вызвать его из упрощения после того, как упростил поддеревья:
-- Tries to match evaluation rules after simplifying subtrees.
simplify :: Expr -> Expr
simplify (Plus a b) = eval (Plus (simplify a) (simplify b))
simplify (Mult a b) = eval (Mult (simplify a) (simplify b))
simplify e = e
Эта версия упрощения имеет много ограничений: она не будет распределять умножение по неконстантному поддереву, она не будет переупорядочивать выражение для объединения константных выражений (поэтому эквивалент 1 + a + 2 не будет упрощается до + 3) и т. д. Тем не менее, он выполняет основные задания.