对整数树求和 (Haskell)

Question

我正在尝试创建一个对非二进制整数树的值求和的函数。

-- datastructures.hs    
data Tree a = Empty | Node a [Tree a] deriving (Eq, Show)

myNums :: (Num a) => Tree a
myNums = Node 1 [ 
           Node 2 [ 
             Node 4 [Empty], Node 5 [Empty]
           ], 
           Node 3 [
             Node 6 [Empty], Node 7 [Empty], Node 8 [Empty] 
           ]
        ]

addNums :: (Num a) => Tree a -> a
addNums Empty = 0
addNums (Node n [Empty]) = n
addNums (Node n (x:xs)) = n + (addNums x) + (addNums xs)

理想情况下，我希望 addNums myNums 为 36，但这会产生错误：

datastructures.hs:20:54:
    Couldn't match expected type ‘Tree a’ with actual type ‘[Tree a]’
    Relevant bindings include
      xs :: [Tree a] (bound at datastructures.hs:20:20)
      x :: Tree a (bound at datastructures.hs:20:18)
      n :: a (bound at datastructures.hs:20:15)
      addNums :: Tree a -> a (bound at datastructures.hs:18:1)
    In the first argument of ‘addNums’, namely ‘xs’
    In the second argument of ‘(+)’, namely ‘(addNums xs)’

我该如何应对，最佳做法是什么？

编辑：最佳实践似乎完全忽略了 Empty！我忘了 [] 是类型 [Tree a] 的有效实例。所以最好的实现方式是：

data Tree a = Node a [Tree a] deriving (Eq, Show)

addNums :: (Num a) => Tree a -> a
addNums (Node n []) = n
addNums (Node n (x:xs)) = n + (addNums x) + addNums (Node 0 xs)

Answer 1

问题出在您 addNums 定义的最后两行。您必须检查空的基本情况，而不是当列表包含其中包含 Empty 的单个元素时。这样的事情应该有效：

addNums :: (Num a) => Tree a -> a
addNums Empty = 0
addNums (Node n []) = n
addNums (Node n (x:xs)) = n + (addNums x) + addNums (Node 0 xs)

请注意，对于空列表，您只是返回 n。当列表有多个元素时，你递归地求和直到它达到 bae 情况（即列表变为空）。

演示 ghci：

λ> addNums myNums
36

Answer 2

可能的解决方案：

addNums :: (Num a) => Tree a -> a
addNums Empty = 0
addNums (Node n xs) = n + sum (map addNums xs)

在递归的情况下，我们有一个树列表 xs。我们可以在每棵树上使用 addNums，获得一个数字列表。然后，我们简单的总结一下，加上根n.

Answer 3

只需导出 Foldable 并使用现有的 sum:

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Empty | Node a [Tree a] deriving (Eq, Show, Foldable)

myNums :: (Num a) => Tree a
myNums = ...

main = print $ sum myNums

对整数树求和 (Haskell)

Summing an Integer Tree (Haskell)

tree

haskell

data-structures