haskell - типы - функции - деревья

Question

Для практики на Haskell я хочу реализовать игру, в которой студенты / ученики должны игриво изучать некоторую алгебру.

В качестве базового типа данных я хочу использовать дерево:

• с узлами, которыехранить метки и алгебраические операторы.
• с листьями, имеющими метки и переменные (тип String) или числа

Теперь я хочу определить что-то вроде

data Tree = Leaf {l :: Label, val :: Expression}
          | Node {l :: Label, f :: Fun, lBranch :: Tree, rBranch :: Tree}

data Fun = "one of [(+),(*),(-),(/),(^)]"

-- type Fun = Int -> Int 

будет работать

Следующее, о чем я думаю, это сделать «эквивалентность» деревьев - так как умножение / сложение коммутативно, и можно упростить сложение умножения и т. д. весь набор алгебраических операций.Я также должен искать по дереву - по меткам, которые я считаю лучшим, это хороший подход.

Любые идеи, какие теги / фразы искать и как решить «Забаву данных».

Answer 1

Чтобы немного расширить ответ Эдварда З. Янга:

Самый простой способ определить ваши операторы здесь, вероятно, как тип данных, наряду с типами атомарных значений в конечных узлах и дереве выражений в целом:

data Fun = Add | Mul | Sub | Div | Exp deriving (Eq, Ord, Show)

data Val a = Lit a | Var String deriving (Eq, Ord, Show)

data ExprTree a = Node String Fun (ExprTree a) (ExprTree a)
                | Leaf String (Val a)
    deriving (Eq, Ord, Show)

Затем вы можете определить ExprTree a как экземпляр Num и еще много чего:

instance (Num a) => Num (ExprTree a) where
    (+) = Node "" Add
    (*) = Node "" Mul
    (-) = Node "" Sub
    negate = Node "" Sub 0
    fromInteger = Leaf "" . Lit

... что позволяет создавать естественные выражения без меток:

*Main> :t 2 + 2
2 + 2 :: (Num t) => t
*Main> 2 + 2 :: ExprTree Int
Node "" Add (Leaf "" (Lit 2)) (Leaf "" (Lit 2))

Также обратите внимание на приведенные выше пункты deriving в определениях данных, в частности Ord; это говорит компилятору автоматически создавать отношение упорядочения для значений этого типа. Это позволяет вам сортировать их последовательно, что означает, что вы можете, например, определить канонический порядок подвыражений, чтобы при перестановке коммутативных операций вы не застревали в цикле. Учитывая некоторые канонические сокращения и подвыражения в каноническом порядке, в большинстве случаев вы сможете использовать автоматическое соотношение равенства, заданное Eq, для проверки эквивалентности подвыражений.

Обратите внимание, что метки будут влиять на порядок и равенство здесь. Если это нежелательно, вам нужно написать собственные определения для Eq и Ord, очень похожие на те, которые я дал для Num.

После этого вы можете написать некоторые функции обхода и сокращения, выполнять такие операции, как применение операторов, выполнение подстановки переменных и т. Д.

Answer 2

Похоже, вы хотите построить систему символической алгебры . Существует обширная и разнообразная литература по этому вопросу.

Вы не хотите представлять операторы как Int -> Intпотому что тогда вы не можете проверить, какую операцию реализует любая данная функция, а затем реализовать оптимизацию глазка для таких вещей, как упрощение и т. д. Таким образом, простой перечислимый тип данных сделает свое дело, а затем напишет функцию eval, которая фактически оценивает ваше дерево.