Find all leafes of a binary searchtree by folding

I got the task of getting all leafs from a binary tree of this datatype:

data Bintree el = Empty |
                  Tree {left :: Bintree el, node :: el, right :: Bintree el} deriving Show

Now I have this Treefold function which works perfectly in tests:

binTreeFold :: (a -> b -> a -> a) -> a -> Bintree b -> a
binTreeFold f el Empty = el 
binTreeFold f el tree@(Tree leftTree node rightTree) = f (binTreeFold f el leftTree) node (binTreeFold f el rightTree)

And I try to get all leafs but somehow it simply doesnt work (Compile issues mentioned below):

leavesWithFold :: Bintree a -> [a]
leavesWithFold Empty = []
leavesWithFold tree =  binTreeFold (\left -> \node -> \right -> if (checkIfTreeIsLeaf node) then left ++ [node] ++ right else left ++ [] ++ right) [] tree

using the following function:

checkIfTreeIsLeaf :: Bintree a -> Bool
checkIfTreeIsLeaf Empty = False
checkIfTreeIsLeaf (Tree Empty node Empty) = True
checkIfTreeIsLeaf _ = False

The compiler tells me

Couldn't match type `a' with `Bintree a0'

But in former functions the use of

left ++ [node] ++ right

Was working perfectly fine. Have you any idea what I did wrong and probably what I could change?

Best Whishes

Solution

Well typically the idea of a using a fold function is that it does all the work for you. So by writing a function that branches into an Empty case and a tree case, this is already a bit strange.

A recursive approach

But let us simply start with a recursive approach. Forget about folding, etc. for now. How would we generate a list of leaves in general?

Well there are basically three cases here:

in case we encounter an Empty, then we return the empty list, since Empty is not a leaf, and we are supposed to return all leaves, so:
```
leaves Empty = []
```
in case we encounter a Tree with Empty both as left and right subtree, we know that that Tree is a leaf, so we return the element it carries, as a list:
```
leaves (Tree Empty x Empty) = [x]
```
in case one of the two subtrees (or both) are not Empty, we recursively would call the leaves function, and concatenate the two together:
```
leaves (Tree l _ r) = leaves l ++ leaves r
```

So now in full we got:

leaves :: Bintree a -> [a]
leaves Empty = []
leaves (Tree Empty x Empty) = [x]
leaves (Tree l x r) = leaves l ++ leaves r

How to detect through recursion that this is a leaf

We of course can not do that with the binTreeFold approach. But can't we detect whether a tree is in fact a leaf? In case the two recursive calls both result in an empty list, we know that the current Bintree is in fact a leaf. Indeed: if the left (and right) subtree are Empty, they result in empty lists. And in case these are not empty, then these either are leaves, that will recursively produce a singleton list, or those are not Trees with descendants, that will eventually lead to leaves, and therefore to non-empty lists.

Encoding this in the fold function

So we an first take a look at the recursive calls, and then based on the fact whether these are both empty lists, either return a singleton list with the leaf element, or concatenate the two lists together, like:

f [] x [] = [x]
f l _ r = l ++ r

Or using this in the binTreeFold function:

leavesWithFold :: Bintree a -> [a]
leavesWithFold = binTreeFold f []
    where f [] x [] = [x]
          f l _ r = l ++ r