haskell - 获取树中定义的整数的总和和乘积

Question

我在理解如何在 Haskell 中执行以下操作时遇到了一些问题:

假设我有一个类似的声明:

a * (b + c)

a + (b * c)

a + (b * ( c + d))

a * (b + ( c * d))

等等

我想在树中表达这些语句并评估每个语句的结果，首先我定义了以下数据结构:

data statement = Number Int 
               | Product statement statement 
               | Sum statement statement
               deriving (Eq, Show)

对于要使用的示例树，我使用了以下函数:

a :: statement
a = Product (Number 2) (Sum (Number 5) (Number 1))

现在我想构建一个函数 treeResult ，它给我我定义的语句的结果，但我不知道如何解决这个问题。上述语句返回的整数应为 12。

我的第一个猜测是编写一个将“语句”作为参数并返回一个 int 的函数，对于初学者来说，它只使用简单的语句。

treeResult :: statement -> Int
treeResult (Number a) = a
treeResult (Product (Number a) (Number b)) = a*b
treeResult (Sum (Number a) (Number b)) = a+b

现在我知道我需要一些递归的东西，但我不知道如何用 haskell 编写它，有人可以帮我吗？

Answer 1

首先:statement需要大写，因为它不是类型变量。但这是最不重要的事情。

treeResult :: Statement -> Int
treeResult (Number x) = x

到目前为止显然是正确的。我们正在匹配 Number构造函数，提取 Int并返回 - 类型良好并做它应该做的。

treeResult (Product (Number a) (Number b)) = a*b
treeResult (Sum (Number a) (Number b)) = a+b

这是类型良好的，但不够通用。在此模式中，您限制了 Product 的字段和 Sum至 Number s，但实际上它们可以是任何 Statement .所以你需要定义 Product/Sum :

treeResult (Product a b) = ...
treeResult (Sum a b) = ...

但我们不能只是将两者相加/相乘 Statements . (+)和 (*)没有为他们定义(我们现在正在这样做)。当一个操作数是 Product ，我们如何得到它作为 Int 的值?通过评估它。 Statement是递归的，所以我们需要递归来评估它。 因此，函数变为

treeResult (Product a b) = (treeResult a) * (treeResult b)
treeResult (Sum a b) = (treeResult a) + (treeResult b)