Implementation of map on binary tree using fold

Question

I'm struggling with define map over tree using foldBT. My idea is to convert the tree into list, map the operator over the list, and then convert the list back to tree. But it sounds inefficient and also doesn't make use of foldBT... I tried to run foldBT (*2) Nil (numTree [3,5,7] but ghci reported error. I don't really understand how the function foldBt works. An example would be great.

data SimpleBT a = Nil | N a (SimpleBT a) (SimpleBT a) deriving (Show, Eq)

foldBT :: (a -> b -> b -> b) -> b -> SimpleBT a -> b
foldBT f e Nil = e
foldBT f e (N a left right) = f a (foldBT f e left) (foldBT f e right)

mapTree :: (a -> b) -> SimpleBT a -> SimpleBT b
mapTree f Nil = Nil
mapTree f (N a left right) = N (f a) (mapTree f left) (mapTree f right)

size :: SimpleBT a -> Int
size Nil = 0
size (N _ left right) = 1 + size left + size right

insert ::  SimpleBT a -> a -> SimpleBT a
insert Nil a = N a Nil Nil
insert (N x left right) a
  | size left <= size right = N x (insert left a) right
  | otherwise = N x left (insert right a)

numTree :: [a] -> SimpleBT a
numTree xs = foldl insert Nil xs

Hint: how would you make a foldBT that leaves the tree intact? — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Feb 16, 2019 at 20:34

Daniel Wagner · Accepted Answer · 2019-02-16 20:39:56Z

5

Let us hypothesize mapTree f = foldBT g e, and solve for g and e. The definition of foldBT says:

foldBT g e Nil = e

Meanwhile, from the definition of mapTree, we get:

mapTree f Nil = Nil

From our hypothesis that mapTree f = foldBT g e, we can transform the second equation and stick it next to the first equation:

foldBT g e Nil = Nil
foldBT g e Nil = e

So e = Nil.

Let's do the other clauses now. The definition of foldBT says:

foldBT g e (N a left right) = g a (foldBT g e left) (foldBT g e right)

Meanwhile, mapTree's definition says:

mapTree f (N a left right) = N (f a) (mapTree f left) (mapTree f right)

Again, using our hypothesis mapTree f = foldBT g e, we can now rewrite this equation, and stick it next to the first one:

foldBT g e (N a left right) = N (f a) (foldBT g e left) (foldBT g e right)
foldBT g e (N a left right) = g a (foldBT g e left) (foldBT g e right)

So g a = N (f a) would validate this equation. Writing these all down in one spot, we get:

mapTree f = foldBT g e where
    e = Nil
    g a = N (f a)

You can inline the definitions of e and g if you like; I would.

mapTree f = foldBT (N . f) Nil

answered Feb 16, 2019 at 20:39

Daniel Wagner

156k10 gold badges231 silver badges393 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Jung Over a year ago

I really like your solution. How do you come to the idea of g /= f

Daniel Wagner Over a year ago

@Jung Your mind should go the other way: why assume g = f to begin with? Never assume an equality until you're forced to! A better question would be, "How did I come to the idea that there might be an equality relating mapTree and foldBT?", and for that, I cheated: you yourself demanded it in the original question text.

Jung Over a year ago

good tip! I do indeed know they are related through the equation mapTree f = foldBT _ e I struggled because I assume g = f But it makes sense that couldnt happen since that would lead to f a = N (f a) Once again thanks !

Robin Zigmond · Accepted Answer · 2019-02-16 20:57:33Z

1

The idea of the foldBT function is that it takes an argument for each constructor of your data type (plus the one holding the whole SimpleBT a itself that you wish to fold over). The first one, of type a -> b -> b -> b corresponds to the recursive N constructor, and shows how to combine the value at the node with the results of the fold of the two subtrees into the result of the entire fold. The second argument corresponds to the Nil constructor, and since this constructor takes no arguments, the corresponding argument to fold is simply a constant.

It's completely analagous to folding over a list. The list type [a] also has 2 constructors. One of them takes an a and a list and adds the element to the front of the list: a -> [a] -> [a], this gives rise to a "fold function" of type a -> b -> b. The other constructor, as in your case, is nullary (the empty list), so again corresponds to an argument whose type is just b. Hence foldr for a list has type (a -> b -> b) -> b -> [a] -> b.

There is a great discussion of this, with more examples, in this chapter of the Haskell wikibook: https://en.wikibooks.org/wiki/Haskell/Other_data_structures

As for how to build a map from a fold, for your particular tree type - bearing in mind what I've said above, you need (given a mapping function f :: a -> a0), we need to think about what this does to both the Nil tree, and what it does recursively to trees with a leaf and 2 branches. Also, since our return type will of course be another tree of the same type, b here will be SimpleBT a0.

For Nil, obviously we want map to leave it unchanged, so the second argument to foldBT will be Nil. And for the other constructor, we want the map to apply the base function to the value at the leaf, and then recursively map over the 2 branches. This leads us to the function \a left right -> N (f a) (mapTree f left) (mapTree f right).

So we can conclude that the map function can be defined as follows (thanks to @DanielWagner and @WillemVanOnsen for helping me fix my first broken version):

mapTree :: (a -> b) -> SimpleBT a -> SimpleBT b
mapTree f = foldBT foldFunc Nil
    where foldFunc a l r = N (f a) l r

edited Feb 16, 2019 at 20:57

answered Feb 16, 2019 at 20:41

Robin Zigmond

18.3k2 gold badges25 silver badges38 bronze badges

4 Comments

willeM_ Van Onsem Over a year ago

In a fold function, the l and r are typically "already folded", so you can simplify the last one to foldFunc a l r = N (f a) l r. You also thus forgo the N constructor :).

Robin Zigmond Over a year ago

Yeah, thanks - I'd just figured both of those out myself. Will edit now :)

Jung Over a year ago

thanks for the reference ! One question: What does the last b in the type signature of foldBT represent ? Does it have the type of Nil which is polymorphic?

Robin Zigmond Over a year ago

The last b is the type of the return value. It's arbitrary, but it determines the types of the arguments, in the way I described: you need a b for the Nil tree, and the function which deals with the N constructor must have type a -> b -> b -> b as it takes the leaf value and the results of folding the subtrees and computes the new result. Again, it's exactly analogous to folding a list, where the type signature is (a -> b -> b) -> b -> [ a] -> b.

Collectives™ on Stack Overflow

Implementation of map on binary tree using fold

2 Answers 2

3 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related