Суммирование целочисленного дерева (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 (список становится пустым).

Demo в 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