总结一个整数树（Haskell） [英] Summing an Integer Tree (Haskell)

问题描述

 我想尝试一个函数来总结非二进制整数树的值。 datastructures.hs 
 data树a =空|节点a [Tree a]导出（Eq，Show）
 
 myNums ::（Num a）=>树a 
 myNums =节点1 [
节点2 [
节点4 [空]，节点5 [空] 
]，
节点3 [
节点6 [空]，节点7 [空]节点8 [空] 
] 
] 
 
 addNums ::（Num a）=>树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：
无法匹配预期类型'Tree a'与实际类型'[Tree a]'
相关绑定包括
 xs :: [Tree a]（绑定在datastructures.hs ：20：20）
x ::树a（绑定在datastructures.hs：20：18）
n :: a（绑定在datastructures.hs：20：15）
 addNums :: Tree a  - > a（绑定在datastructures.hs：18：1）
在'addNums'的第一个参数中，即'xs'
在'（+）'的第二个参数中，即'（addNums xs） '
  

我如何解决这个问题，最好的做法是什么？

编辑：最佳做法似乎省略了 Empty 我忘了 [] 是 [Tree a] 的有效实例。所以实现这个的最好方法是：

 数据树a =节点a [Tree a]派生（Eq，Show）
 
 addNums ::（Num a）=>树a  - > a 
 addNums（Node n []）= n 
 addNums（Node n（x：xs））= n +（addNums x）+ addNums（Node 0 xs）
  

解决方案

问题出在你的 addNums 定义。您必须检查空的基本情况，而不是列表中包含单个元素，其中包含 Empty 。这样的东西应该可以工作：

  addNums ::（Num a）=>树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 
  

I'm trying to make a function that sums up the values of a non-binary integer tree.

-- 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)

Ideally, I would like addNums myNums to be 36, but this produces an error:

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)’

How do I counter this, and what are the best practices?

EDIT: Best practices seem to omit Empty altogether! I forgot that [] is a valid instance of type [Tree a]. So the best way to implement this is:

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)

解决方案

The problem is in the last two lines of your addNums definition. You have to check for the empty base case, not when the list contains a single element with Empty inside it. Something like this should work:

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)

Note that for an empty list you are just returning n. And when the list has more than one elements, you recursively sum it untill it reaches the bae case (i.e the list becomes empty).

Demo in ghci:

λ> addNums myNums
36

这篇关于总结一个整数树（Haskell）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！