CODEWITHSUNDEEP
haskelltreebinaryfoldmap-function
maxloo
maxloo

Reputation: 491

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

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)

Upvotes: 3

Views: 691

Answers (1)

K. A. Buhr
K. A. Buhr

Reputation: 50864

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.

Upvotes: 2

Related Questions