CODEWITHSUNDEEP
haskellbinary-treefold
Jung
Jung

Reputation: 139

Implementation of map on binary tree using fold

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

Upvotes: 1

Views: 382

Answers (2)

Robin Zigmond
Robin Zigmond

Reputation: 18249

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

Upvotes: 1

Daniel Wagner
Daniel Wagner

Reputation: 152817

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

Upvotes: 5

Related Questions