haskell - 类型 - 函数 - 树

Question

对于haskell练习,我想实现一个游戏,学生/学生应该开玩笑地学习一些代数.

作为基本数据类型,我想使用树:

• 具有存储标签和代数运算符的节点.
• 带有标签和变量(类型字符串)或数字的叶子

现在我想定义类似的东西

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

为了扩展Edward Z. Yang的答案:

在这里定义运算符的最简单方法可能是作为数据类型,以及叶节点中的原子值类型和表达式树的整体类型:

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.

之后,您可以编写一些遍历和缩减函数,以执行诸如应用运算符,执行变量替换等操作.