Higher Order Haskell Functions Applied to Trees

Question

I have the data type

data Tree a = Null | Node a {lTree, rTree :: Tree a}

I want to rewrite the following higher order functions so that they can apply to trees.

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

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

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

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

filter :: (a -> Bool) -> Tree a -> Tree a 

zip :: Tree a -> Tree b -> Tree (a,b)

I want to know how to write the functions explicitly, for example I know that the map function can be written:

treeMap :: (a ->b) -> Tree a -> Tree b 
treeMap f tree = case tree of 
    Null -> Null 
    Node a Null Null -> Node (f a) Null Null 
    Node a l r -> Node (f a) (treeMap f l) (treeMap f r)

With the pragmas {-# LANGUAGE DeriveFunctor, DeriveFoldable #-} you can just add ... deriving (Functor, Foldable) to the data declaration and GHC will do the first four for you. — ErikR
@BenjaminHodgson if the top node's value is eliminated, the two updated branches can be joined by pulling up the rightmost element from the left, or leftmost from the right updated branch. — Will Ness
@WillNess, as we know nothing about what the tree means, we have no particular reason to believe that the operation you suggest makes any sense. — dfeuer
@dfeuer my suggestion follows the "lisp congruency", same as chi's answer. both make sense or don't in the same way, I think. so yes, of course it's somewhat arbitrary. (that's why I said "can", and not e.g. "must"; indeed I should've perhaps said "may" or even "might" :) ). — Will Ness

chi chi · Accepted Answer · 2016-05-27T12:31:41

Here's a step-by-step approach. We will focus on treeFoldr, only.

The basic and boring way

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

We start from a basic approach to define treeFoldr: we convert to list first, then use foldr.

-- In-order visit
toList :: Tree a -> [a]
toList Null = []
toList (Node l a r) = toList l ++ [a] ++ toList r

treeFoldr_1 :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr_1 f x t = foldr f x $ toList t

Equational reasoning to the rescue

Now we transform treeFoldr_1 into a recursive definition, removing the intermediate list and the foldr call.

We split the definition of treeFoldr_1, by cases on t.

treeFoldr_2 :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr_2 f x Null         = foldr f x $ toList Null
treeFoldr_2 f x (Node l a r) = foldr f x $ toList (Node l a r)

We expand toList.

treeFoldr_3 :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr_3 f x Null         = foldr f x []
treeFoldr_3 f x (Node l a r) = foldr f x (toList l ++ [a] ++ toList r)

Here we exploit a foldr property:

--   foldr f x (ys ++ zs) = foldr f (foldr f x zs) ys

obtaining

treeFoldr_4 :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr_4 _ x Null         = x
treeFoldr_4 f x (Node l a r) = 
    foldr f (foldr f x ([a] ++ toList r)) (toList l)

Again, we apply the same foldr equation.

treeFoldr_5 :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr_5 _ x Null         = x
treeFoldr_5 f x (Node l a r) = 
    foldr f (foldr f (foldr f x (toList r)) [a]) (toList l)

By definition of foldr, we can simplify

--    foldr f z [a] = f a z

obtaining

treeFoldr_6 :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr_6 _ x Null         = x
treeFoldr_6 f x (Node l a r) = 
    foldr f (f a (foldr f x (toList r))) (toList l)
              -- ^^^^^^^^^^^^^^^^^^^^^^

Now, foldr f x (toList t) is treeFoldr f x t, so we can try a recursive call to replace that pattern.

treeFoldr_7 :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr_7 _ x Null         = x
treeFoldr_7 f x (Node l a r) = 
    foldr f (f a (treeFoldr_7 f x r)) (toList l)
 -- ^^^^^^^...........................^^^^^^^^^^

Again, same pattern.

treeFoldr_8 :: (a -> b -> b) -> b -> Tree a -> b
treeFoldr_8 _ x Null         = x
treeFoldr_8 f x (Node l a r) = 
    treeFoldr_8 f (f a (treeFoldr_8 f x r)) l

... and we are done. No more lists around!

Small test

test :: Tree Int
test = Node 
       (Node Null 2 Null) 
       5 
       (Node
        (Node Null 4 Null)
        1
        (Node Null 7 Null))

foo :: Int -> String -> String
foo n s = "(" ++ show n ++ ", " ++ s ++ ")"

--  *TreeFoldable> treeFoldr_8 foo "X" test 
--  "(2, (5, (4, (1, (7, X)))))"

Higher Order Haskell Functions Applied to Trees

2 Answers

The basic and boring way

Equational reasoning to the rescue

Small test