查找叶子总和 [英] Find Sum of leaves

问题描述

我应该写这样的代码

具有任意数量的子节点的多态树类型可能表示如下(请注意，叶子存储一个列表，内部节点存储"ListTree"的列表):

A polymorphic tree type with nodes of an arbitrary number of children might be represented as follows (note that the leaves store a list, and interior nodes store list of "ListTree"s):

data ListTree a = ListLEAF [a] | ListNODE [(ListTree a)]
 deriving (Show, Read, Eq)

编写一个函数foldListTree，该函数接受一个函数(f)，一个基值(base)和一个ListTree(t)，并将树中叶注释列表中的值组合在一起t通过应用功能f. (从左到右扫描树的叶子). foldListTree的调用方式为:

Write a function foldListTree that takes a function (f), a base value (base), and a ListTree (t) and combines the values in the lists of the leaf notes in tree t by applying function f. (The leaves of the tree are scanned from left to right). foldListTree is invoked as:

foldListTree f base t，其中f是类型a->a->a的组合函数. foldListTree的类型应为:

foldListTree f base t where f is the combining function of type a->a->a. The type of foldListTree should be:

foldListTree :: (a -> a -> a) -> a -> ListTree a -> a

我正在尝试读取列表中的每个节点，但我想它正在陷入无限循环.

I am trying to read every node in the list but I guess it's getting into an infinite loop.

data ListTree a = ListLEAF [a] | ListNODE [(ListTree a)] deriving (Show, Read, Eq)


foldListTree :: (Num a) => (a -> a -> a) -> a -> ListTree a -> a 
foldListTree op base (ListLEAF []) = base
foldListTree op base (ListNODE []) = base
foldListTree op base (ListLEAF [a]) = foldr op base [a]
foldListTree op base (ListNODE b) = (op (foldListTree op base x) 
                                        (foldListTree op base (ListNODE xs)))
                                        where x:xs = b

t4 = ListNODE
       [ ListNODE
           [ ListLEAF [1,2,3]
           , ListLEAF [4,5]
           , ListNODE [ListLEAF [6], ListLEAF []]
           ]
       , ListNODE []
       , ListLEAF [7,8]
       , ListNODE [ListLEAF [], ListLEAF []]
       ]

命令:foldListTree (+) 0 t4

>错误:***异常:indi.hs:(86,1)-(90,54):函数foldListTree

推荐答案

如果您打开

It really helps if you turn on -Wall since Haskell can provide you a list of the patterns you did not cover.

主要问题是您编写为模式:

The main problem is that you wrote as pattern:

foldListTree op base (ListLEAF [a]) = foldr op base [a]

因此，这意味着您将模式限制为单例列表.代码中无处没有ListLEAF构造函数的模式，该模式采用具有任意数量元素的列表.

So that means you restricted the pattern to singleton lists. Nowhere in the code, is there a pattern for a ListLEAF constructor that takes a list with an arbitrary number of elements.

不过，通过实现两种情况，可以使上述操作更加简单:每个构造函数一个.在ListNODE情况下，我们可以将foldListTree用作折叠功能:

You can however make the above a lot simpler by implementing two cases: one for each constructor. We can use foldListTree as folding function in the ListNODE case:

foldListTree :: Num a => (a -> a -> a) -> a -> ListTree a -> a 
foldListTree op base (ListLEAF x) = foldr op base x
foldListTree op base (ListNODE b) = foldr (flip (foldListTree op)) base b

这给了我们

Prelude> foldListTree (+) 0 t4
36

注意:尽管严格说来没错，但我发现在所有大写字母中都写上LEAF和NODE很奇怪，通常一个人用驼峰式写，所以ListLeaf和ListNode

Note: Although strictly speaking not wrong, I find it odd to write LEAF and NODE in all caps, usually one writes this in camelcase, so ListLeaf and ListNode.

 

注意:最好在ListLeaf中存储a，而不是[a]，因为这样可以给您更多的存储空间.它完全没有排除将列表存储在叶子中的可能性，但是您将决定权留给数据类型的用户.

Note: It might be better that your ListLeaf stores an a, not an [a], since then you give more freedom what to store in your leaves. It does not exclude the possibility at all to store lists in the leaves, but you leave that decision to the user of the data type.

这篇关于查找叶子总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！