CODEWITHSUNDEEP
haskellfunctional-programmingbinary-tree
newb346
newb346

Reputation: 165

Attempting to flatten a tree in Haskell using in-order traversal

Trying to use the given fold function to flatten out a tree into a list.

treeFold :: (b -> a -> b -> b) -> b -> Tree a -> b
treeFold _ b Leaf         = b
treeFold f b (Node lt x rt) = f (treeFold f b lt) x (treeFold f b rt)

Here is what I have tried to so far:

treeToList :: Tree a -> [a]
treeToList = treeFold (\xs x ys -> xs ++ x : ys) (\x -> [x])

For some reason, I can't quite wrap my head around how to go about doing this? Feels like there's something I haven't quite gotten into my head about Haskell. Any help would be appreciated along with how to go about solving it. Thanks!

Edit:

I realize that the type signature I am using here verges on the nonsensical. In the type signature of treeFold, based on what I can think, the second argument (b) is probably a list since it acts as the accumulator in a way in this case. That would make the third argument (Tree a) a some version of the argument on the left of the equation. Two of the arguments within the function have to be the left and right subtrees within a Node. The third argument is just the value of the Node. Within the function, I need to combine the left tree, right tree and the value in the usual in order fashion but all the different variations I tried have had some issues

Upvotes: 2

Views: 543

Answers (2)

Will Ness
Will Ness

Reputation: 71070

The types must fit:

treeFold ::           ( b -> a -> b -> b              ) -> b -> Tree a -> b

treeToList = treeFold (\xs   x    ys -> xs ++ (x : ys))    z
-------------------------------------------------------------------
                        b    a    b     b      a   b       b
                                              --------
                                              b

Since x and ys participate in the same :, their types must be compatible:

(:) ::   a  -> [a]  ->  [a]
x   ::   a
ys  ::          b
-------------------
              b ~ [a]

Thus we have

treeFold ::           ( [a] -> a -> [a] -> [a]           ) -> [a] -> Tree a->[a]

treeToList = treeFold (\ xs    x    ys  -> xs ++ (x : ys))     z
-------------------------------------------------------------------
                         [a]   a    [a]    [a]    a   [a]     [a]
                                                 --------
                                                 [a]

Conclusion: the last argument, z, must have the type [a].

What is the meaning of this argument? As usual with the folds, each "variant" in the data type definition has a corresponding argument to the fold function.

Your (missing) data type definition is:

data Tree a = Node (Tree a)    a   (Tree a)       | Leaf

and the fold's type is

treeFold ::   (         b  ->  a  ->  b  -> b )   ->  b     -> Tree a -> b

which corresponds to the "recursive results-holding type" of

data TreeF a r = NodeF  r      a      r           | LeafF

Thus z is "the value to convert each Leaf to".

Most natural choice for it is just []. Actually, the only choice, because we don't know anything about the type a (in [a]) yet.

Upvotes: 4

melpomene
melpomene

Reputation: 85757

The type of treeFold is

treeFold :: (b -> a -> b -> b) -> b -> Tree a -> b

You want to return a list of values, [a].

Therefore the result type b must be equal to [a], giving us a specialized type signature of

treeFold :: ([a] -> a -> [a] -> [a]) -> [a] -> Tree a -> [a]

Note that the second argument has type [a].

What value are you passing instead?

Upvotes: 4

Related Questions