Can't figure out how to properly type my N-ary tree

user_11360093 0
Viewed 48

I made the following N-ary tree data type:

data Tree a = Leaf a | Node a [Tree a] deriving (Show)

with the following method:

listLeaf::Tree a -> [a]
listLeaf (Leaf a) = [a]
listLeaf (Node a (l:list)) = concat $ listLeaf l

I'm trying to make listLeaf so that it gives me a list that contains each element of a leaf inside my tree. This means that if I have the following tree: Node 3 [Leaf 1, Leaf 2, Node 1 [Leaf 3]], my objective would be to get [1,2,3].

As you probably noticed the type of my function doesn't add up because it expects a list of a, but I'm giving it a list of lists. Can't wrap my head around how I can have the base case (leaf) return me a type [a] and at the same time have the Node case give me the same kind of type. I feel like I need to use a higher order function aside from concat, but I got no clue. Any hints?

haskell
1 Answers

You are here only calling listLeaf on l, the first element of the list, so you will only obtain the leftmost leaf. Furthermor concat then does not make much sense, ince you have a list of values, not a list of lists of values.

You can use concatMap :: (a -> [b]) -> [a] -> [b] to perform a mapping on all elements and concatenate the lists of the results, so:

listLeaf :: Tree a -> [a]
listLeaf (Leaf a) = [a]
listLeaf (Node _ cs) = concatMap listLeaf cs
user_675790
Related