Haskell - How to create a mapTree function based on a foldr of a BinaryTree?

Question

This is a question from Chapter 11, Algebraic Datatypes of "Haskell Programming from first principles":

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

We do not actually insert a value into an existing tree; each time we want to insert a value into the data structure, we build a whole new tree:

insert' :: Ord a => a -> BinaryTree a -> BinaryTree a
insert' b Leaf = Node Leaf b Leaf
insert' b (Node left a right)
  | b == a = Node left a right
  | b < a = Node (insert' b left) a right
  | b > a = Node left a (insert' b right)

This is a map function for the data structure of BinaryTree:

mapTree :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree _ Leaf = Leaf
mapTree f (Node left a right) = 
  Node (mapTree f left) (f a) (mapTree f right)

Write foldr for BinaryTree

Given the definition of BinaryTree we have provided, write a catamorphism for the binary trees.

-- any traversal order is fine
foldTree :: (a -> b -> b) 
  -> b 
  -> BinaryTree a 
  -> b

The type above is a hint for those that don’t convert the tree into a list before applying the folding function.

Rewrite map for BinaryTree

Using the foldTree you just wrote, rewrite mapTree using foldTree. The absence of an Ord constraint is intentional, you don’t need to use the insert function.

mapTree' :: (a -> b)
  -> BinaryTree a
  -> BinaryTree b
mapTree' f bt =
  foldTree undefined undefined undefined

I managed to get an answer that works for the first question about foldr with a lot of help from: https://github.com/johnchandlerburnham/hpfp/blob/master/11/BinaryTree.hs

My answer:

foldTree f b Leaf = b
foldTree f b (Node left a right) 
  = (foldTree f tempb left) where
    tempb = (f a) tempright
    tempright = foldTree f b right

However, for the second question about writing a new mapTree for BinaryTree, I could not find an answer to that. The original mapTree is provided above. Even the answer at the johnchandlerburnham link uses a different foldtree.

Could someone please help get a workable answer for the second question based on my answer to the first question? Or is another answer for the first question required?

A tree for testing could be:

testTree :: BinaryTree Integer
testTree =
  Node (Node Leaf 3 Leaf) 1 (Node Leaf 4 Leaf)

That does not look like a catamorphism to me. To have cata on trees, we should have a signature like foldTree :: (b -> a -> b -> b) -> b -> BinaryTree a -> b, with the additional b -> representing the left subtree. Are you sure about that signature? It looks like there is some confusion between foldr as in Foldable (which flattens the tree into a list) and cata which preserves the full structure (being the catamorphism). You need the latter for mapTree (it is called foldTree1 in that file, IIUC). — chi
@chi: Thanks, I'm new to catamorphism, so I'm still feeling my way around this. Maybe the second question about mapping is wrong, is my answer to the first question ok? The book says that "catamorphism is a means of breaking down the structure of any datatype", and that's in another chapter about "Folding Lists". It then gives 3 examples I don't quite understand, 2 of which are data Bool = False | True bool :: a -> a -> Bool -> a, and data Maybe a = Nothing | Just a maybe :: b -> (a -> b) -> Maybe a -> b. — maxloo
@chi: The third example is data Either a b = Left a | Right b either :: (a -> c) -> (b -> c) -> Either a b -> c. The book just says "See if you can notice a pattern". Can you notice any pattern? — maxloo
Understanding catamorphisms requires some effort. There are many ways to introduce them. One of them is: cata replaces constructor applications with arbitrary function applications. E.g. a value of type Node Leaf 3 (Node Leaf 4 Leaf) can be applied to foldTree node leaf and the result is (the evaluation of) node leaf 3 (node leaf 4 leaf), where node and leaf are arbitrary arguments. To type check, we need a constant leaf :: b and a function node :: b -> Int -> b -> b as arguments for foldTree (possibly further generalizing Int to a). — chi
maybe does the same. maybe n j applied to Nothing outputs n, and applied to Just x outputs j x -- again, replacing constructors with arbitrary functions/constants. foldr c n similarly maps 1 : 2 : [] which is (:) 1 ((:) 2 []) to c 1 (c 2 n) and is a catamorphism for lists. — chi

K. A. Buhr K. A. Buhr · Accepted Answer · 2020-08-23T17:39:38

You can't write mapTree using a foldTree with that signature. (As @chi notes, the technical problem is that foldTree has the wrong signature to be a true catamorphism for BinaryTree.) In fact, if you load up that linked Haskell file BinaryTree.hs, you'll see that the mapTree' there doesn't work correctly:

λ> :l BinaryTree
λ> mapTree (+1) testTree
Node (Node Leaf 2 Leaf) 3 (Node Leaf 4 Leaf)
λ> mapTree' (+1) testTree
Node (Node (Node Leaf 3 Leaf) 2 Leaf) 4 Leaf

It gives the right node values, but the structure of the tree is wrong.

I don't have a copy of that book, so I can't see exactly what you're seeing, but maybe these notes will be helpful. At the end of section 11.15, the author talks about 2-parameter and 3-parameter versions of foldTree, and shows that only mapTree' written to use the 3-parameter version will work correctly.

Haskell - How to create a mapTree function based on a foldr of a BinaryTree?

1 Answers