求和整数树(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

只需派生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