haskell中树的和

Question

我尝试了下面的代码，但我得到了一个错误，a与预期的类型"Integer"。

data Tree a = Tip | Bin (Tree a) a (Tree a)
sumTree :: Num a => Tree a -> a
sumTotal = 0
sumTree Tip = 0
sumTree (Bin l a r) = (sumTotal+ a)+ sumTree l + sumTree 

Answer 1

在Haskell中没有可变变量，所以sumTotal和sumTotal +没有意义。在Haskell中，通常使用递归作为访问树中的项的机制。因此，您可以将sumTree实现为:

sumTree :: Num a => Tree a -> a
sumTree Tip = 0
sumTree (Bin l a r) = a + sumTree l + sumTree r

对于两层树，这将在左子树和右子树上执行递归。对于像Bin (Bin Tip 1 (Bin Tip 4 Tip)) 2 (Bin Tip 5 Tip)这样的树，这将计算为:

sumTree Bin (Bin Tip 1 (Bin Tip 4 Tip)) 2 (Bin Tip 5 Tip)
→ 2 + sumTree (Bin Tip 1 (Bin Tip 4 Tip)) + sumTree (Bin Tip 5 Tip)
→ 2 + (1 + sumTree Tip + sumTree (Bin Tip 4 Tip)) + sumTree (Bin Tip 5 Tip)
→ 2 + (1 + 0 + (4 + sumTree Tip + sumTree Tip)) + sumTree (Bin Tip 5 Tip)
→ 2 + (1 + 0 + (4 + 0 + sumTree Tip)) + sumTree (Bin Tip 5 Tip)
→ 2 + (1 + 0 + (4 + 0 + 0)) + sumTree (Bin Tip 5 Tip)
→ 2 + (1 + 0 + 4) + sumTree (Bin Tip 5 Tip)
→ 2 + 5 + sumTree (Bin Tip 5 Tip)
→ 2 + 5 + (5 + sumTree Tip + sumTree Tip)
→ 2 + 5 + (5 + 0 + sumTree Tip)
→ 2 + 5 + (5 + 0 + 0)
→ 2 + 5 + 5
→ 7 + 5
→ 12

您也可以使用DeriveFoldable使Tree成为Foldable的实例扩展[ghc-doc](或通过自己实现Foldable实例)。在这种情况下，sumTree只是sum :: (Foldable f, Num a) => f a -> a的一个特例:

{-# LANGUAGEDeriveFoldable#-}
data Tree a = Tip | Bin (Tree a) a (Tree a)deriving Foldable
sumTree :: Num a => Tree a -> a
sumTree =sum

Answer 2

这个错误是由于在多态函数sumTree中使用sumTotal时引用了一个单态类型而导致的。

在

中也有复制粘贴的错别字

sumTree (Bin l a r) = (sumTotal+ a)+ sumTree l + sumTree

但实际上必须有

sumTree (Bin l a r) = (sumTotal+ a)+ sumTree l + sumTree r

，否则你会得到一个不同的错误。

---

但是sumTotal实际上根本不需要，因为它总是0，所以它没有改变什么。你可以把它从任何地方删除，当你这样做的时候，错误就会消失，函数就会正常工作。

但是添加0应该没有伤害，你问吗?对，但是有了这个限制，变量sumTotal得到了一个单态的，即特定的类型，就像Integer一样。并且您的函数sumTree被声明为多态，因此保持这种方式。添加一个固定的类型值一个灵活的类型值毫无意义。

在Haskell中，没有类型强制转换在运行时改变值。所有类型都是事先知道的。当我们将两个"灵活的"多态类型值加在一起时，结果是相同的类型，因此当实际确定该类型具体是什么时，它将被一致地分配给所有三个出现。但是当你使用特定类型的其中之一,你防止同步性。但是，添加0不应该破坏东西，你说。在不更改代码的情况下如何避免错误?

为此，需要禁用单态限制。

在GHCi中使用

> :set -XNoMonomorphismRestriction

，然后在多行输入模式下，使用:{和:}命令重新输入您的定义。

或者在源代码文件中添加

{-# LANGUAGE NoMonomorphismRestriction #-}

在最上面