How to write a function of type a-> b -> b -> b fo

Question

Some background: I have a foldT function (like foldr but for trees) of the following type in Haskell.

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

This foldT only takes type (a -> b -> b -> b) as an input function.

I am trying to find a way to convert my tree into a list, and cannot figure out a way to make my append function take the form (a -> b -> b -> b).

The following is ineffective because it is not the correct type:

append x y z = append x:y:z 

Any help would be appreciated.

Thank you!

Answer 1

If you want to convert the tree onto a list then the function is relatively easy, so basically if you have tree structure such as:

data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Eq, Ord, Show)

Then you'd have to extract the value from the tree and add the first value onto an empty list, then apply the same method to the other branches of the tree recursively with the help of the list (++) operator to append all results onto a single list, i.e.:

toList :: Tree a -> [a]
toList Leaf                    =    []
toList (Node left value right) =    [value] ++ toList left ++ toList right

then to fold it, first:

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

The function signature is missing an argument here lets look at the signature: a(first argument) -> b (second) -> b (third) -> b (return type) the function takes 3 arguments/parameters but the signature you provided only has 1 b type (which im guessing is your accumulator), so basically this would be the function signature you're looking for:

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

Now we can work with this signature, then let's move onto the function:

foldT :: (a -> b -> b) -> b -> Tree a -> b
foldT f acc Leaf                    =   acc
foldT f acc (Node left value right) =   foldT f (foldT f (f value acc) left) right

Although I don't think I should be giving you the answer and you should practice a bit more with recursive data structures so you can better understand how to traverse through them.

PS: If you're going to down vote me, then at least explain why!

Answer 2

Yuck, why are you writing code? GHC can automatically fill in an instance of the Foldable class, which contains the toList you're looking for.

{-# LANGUAGE DeriveFoldable #-}
data Tree a = Leaf | Node a (Tree a) (Tree a) deriving Foldable

treeToList :: Tree a -> [a]
treeToList = toList

This definition of treeToList will perform a pre-order traversal because of the order of the fields of the Node constructor.

Answer 3

As you haven't posted it, I will assume your tree is...

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

... and that the a -> b -> b -> b argument to foldT takes the fields of the Node constructor in the same order they were declared.

I am trying to find a way to convert my tree into a list

Let's begin tackling this by following the types:

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

You want to flatten it into a list, so the result type of your function must be [a]:

treeToList :: Tree a -> [a]

That give us a good idea on how to continue:

treeToList t = foldT f z t

With:

f :: a -> [a] -> [a] -> [a]
z :: [a]
t :: Tree a

Now, onward to the arguments. z is what will be inserted in lieu of the valueless Leafs, and so it must be []. As for f, it must combine the sublists created from the left and right branches with the value directly in the Node. Assuming an in-order traversal, we have:

 treeToList t = foldT (\x l r -> l ++ x : r) [] t

Or, without mentioning t:

 treeToList = foldT (\x l r -> l ++ x : r) []

And that's it. One caveat is that repeatedly using left-nested (++) (which will happen in this case, as foldT walks down the branches recursively) can get quite inefficient. In a situation in which you would care about performance it would be worth considering alternative ways of implementing the concatenating function, such as difference lists.

P.S.: A note about terminology. Saying that a function is "like foldr but for trees" is ambiguous, as there are two well-known kinds of functions analogous to foldr. First, you have the methods of the Foldable class (cf. Benjamin Hodgson's answer), which flatten the tree into a list as they fold it, no matter what you do. Then there are the more powerful catamorphisms, such as the foldT you are using, which are able to make use of the tree structure.

Answer 4

The first thing you start with every time is just to start matching patterns :) At that point, it's pretty much mechanical!

Assuming you have:

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

Let's start matching patterns! :)

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z ...

What's the first Tree constructor? It's Leaf!

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z Leaf = ...

What could we put there? We need something of type b...and we only have one one way to get it. by using z :)

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z Leaf = z

And so, mechanically, we can move on to the next possible pattern:

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z Leaf           = z
foldT f z (Node t1 x t2) =

Well, we can just make it z, but that's a little boring. We probably want to use t1, x, and t2. We can use f, which needs something of type a...and we have x :: a :)

foldT :: (a -> b -> b -> b) -> b -> Tree a -> b
foldT f z Leaf           = z
foldT f z (Node t1 x t2) = f x ??? ???

f has two more arguments, of type b, so what do you think we could put there? We can put z twice, but that's a little boring. How can we get b's from t1 and t2?