Find Sum of leaves

Question

I am supposed to write a code such that

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)

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 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 []]
       ]

Command: foldListTree (+) 0 t4

> Error : *** Exception: indi.hs:(86,1)-(90,54): Non-exhaustive patterns in function foldListTree

It is not entirely clear to me why a leaf has a list of values... — Willem Van Onsem, Sep 23 '19 at 09:18
@WillemVanOnsem perhaps for the [possibility of efficient `uncons`](https://stackoverflow.com/questions/43941551/explicit-purely-functional-data-structure-for-difference-lists/43945275#43945275) operation rearranging the tail so that each leaf element is accessed in amortized O(1) time, and appending to (and accessing past) the end of infinite lists is also then possible. — Will Ness, Sep 23 '19 at 10:06
@WillNess: but one can simply use the `ListTree [a]` in case we want to do that, by specifying it as a list at the `data` level, it looks like overrestricting :) We thus can make a more generic data type, and define an algorithm on more specific subsets of that data type. Tailoring data towards a certain application, looks a bit ugly imho. Somehow in webserver development, it frequently goes wrong if people model for example a database towards a user interface for example. — Willem Van Onsem, Sep 23 '19 at 10:09
@WillemVanOnsem I don't understand, if I have a list of Ints, do you mean I'd have to declare `xs :: ListTree [Int]`? that would be terribly confusing, IMO. — Will Ness, Sep 23 '19 at 10:38
@WillNess: no, you can just make a type synonym `type DList a = ListTree [a]`, such that you have a more "clean" data type, and you make it more clear that you work on a difference list. It means for once we can "have the cake and eat it at the same time" :) — Willem Van Onsem, Sep 23 '19 at 10:40
@WillemVanOnsem with what data type definition for `ListTree`, please? — Will Ness, Sep 23 '19 at 10:54
@WillNess: `data ListTree a = ListLeaf a | Node [ListTree a]`, or in case of your `DList` likely `ListTree a = Leaf a | Node (ListTree a) (ListTree a)`. — Willem Van Onsem, Sep 23 '19 at 11:07
@WillemVanOnsem with the first definition, `type DList a = ListTree [a]` === `data DList a = Leaf [a] | Node [ListTree [a]] = Leaf [a] | Node [DList a]`, isn't it, which is exactly the type in the question. Same with my definition, AFAICT. ... okay, I guess this is what you meant. — Will Ness, Sep 23 '19 at 11:55
@WillNess: exactly, but with that difference, that one can use a `ListTree Int` as well, whereas a `DList` can not do that. So we have generalized it, and at the same time can use a `DList` for lists, so that means that defining it with a list in the *`data` definition*, would needlessly restrict yourself. I somehow have the idea that you here proof the point yourself that using a list in the definition, would result in more types, and more code. — Willem Van Onsem, Sep 23 '19 at 11:57
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/199840/discussion-between-will-ness-and-willem-van-onsem). — Will Ness, Sep 23 '19 at 12:05
@WillemVanOnsem the semantics of the two types are significantly different, e.g. `uncons` would be implemented radically differently (so `type` is no good), so I think I prefer to keep them separate after all and just implement the two almost unrelated types directly, each of them (`newtype` needs an extra constructor tag, which is inconvenient). why connect them when there's no connection, really. — Will Ness, Sep 23 '19 at 16:35

score 3 · Answer 1 · answered Sep 23 '19 at 09:27

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]

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.

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

This gives us:

Prelude> foldListTree (+) 0 t4
36

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.

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.

Find Sum of leaves

1 Answers1

Linked