Haskell foldr function in instance Foldable

data Tree a = Empty | Tree a (Tree a) (Tree a)
deriving (Show, Eq, Read)

I have this data Tree in my programm and i need a foldr funtion in instance Foldable Tree where. The Function should go first through pivot element then smaller tree and then bigger tree.

But i couldn't figure out how to go first with pivot element. I mean, how can i find the pivot Element in a tree in Haskell?

I used quicksort before, which use a pivot element to sort a list.(thats actually what i understood from quicksort) But i don't know how to search(or find) the pivot in a list or in a tree.

here is a example:

foldr (++) [] (Tree "m" (Tree "b" (Tree "a" Empty Empty) (Tree "g" Empty Empty)) (Tree "z" Empty Empty))

and the output should seem like this

"mbagz"

instance Foldable Tree
 where
    foldr _ b Empty = b
    foldr op b (Tree val left right) = foldr op (foldr op (op val b) left) right

I did already implement a foldr function but it works not exactly what i want.

Solution

It depends on how you want to process the elements. This can be done in preorder, inorder or postorder.

For preorder we first process the element, and then recurse on the left and right subtree, so:

-- preorder
preFoldr op z = go
  where go Empty = z
        go (Tree val left right) = val `op` go left `op` go right

-- postorder
postFoldr op z = go
  where go Empty = z
        go (Tree val left right) = go left `op` go right `op` val

-- inorder
inFoldr op z = go
  where go Empty = z
        go (Tree val left right) = go left `op` val `op` go right

The type signatures here are however (a -> a -> a) -> a -> Tree a -> a, it thus can only work if the result and the item of the Tree have the same type. Foldable requires that the result can have a different type. We can however work with this with:

-- preorder
preFoldr op z Empty = z
preFoldr op z (Tree val left right) = val `op` preFoldr op (preFoldr op z right) left

-- postorder
postFoldr op z Empty = z
postFoldr op z (Tree val left right) = postFoldr op (postFoldr op (val `op` z) right) left

-- inorder
inFoldr op z Empty = z
inFoldr op z (Tree val left right) = inFoldr op (val `op` inFoldr op z right) left

For the same tree:

    m
   / \
  b   z
 / \
a   g

these then produce:

Prelude> preFoldr (:) [] t
["m","b","a","g","z"]
Prelude> postFoldr (:) [] t
["a","g","b","z","m"]
Prelude> inFoldr (:) [] t
["a","b","g","m","z"]