获取树中定义的积分的总和和乘积

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.

我的第一个猜测是编写一个函数,它将"statement"作为参数并返回一个int,仅对于简单语句的starters.

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以NumberS,但事实上它们可以是任何Statement.所以你需要定义Product/ Sum:

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

但我们不能只添加/增加两者Statements.(+)并(*)没有为他们定义(我们现在正在那样做).当一个操作数是a时Product,我们如何得到它的值Int？通过评估它.Statement是递归的,所以我们需要递归来评估它.因此,功能变为

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