Haskell binary tree function (map)
You can declare an instance of a class Functor
. This is a standard class for data types that allow a function to be displayed. Note that the type is the fmap
same as the type mapT
:
class Functor f where
fmap :: (a -> b) -> f a -> f b
Suppose your tree is defined as
data Tree a = Node (Tree a) (Tree a) | Leaf a
deriving (Show)
Then you can declare an instance Functor
like this:
instance Functor Tree where
fmap f (Node l r) = Node (fmap f l) (fmap f r)
fmap f (Leaf x) = Leaf (f x)
Here's how you can use it:
main = do
let t = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
let f = show . (2^)
putStrLn $ "Old Tree: " ++ (show t)
putStrLn $ "New Tree: " ++ (show . fmap f $ t)
Output:
Old Tree: Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
New Tree: Node (Node (Leaf "2") (Leaf "4")) (Leaf "8")
You can also define for convenience:
mapT = fmap
Of course, you can do this without typeclasses, but it makes the code more readable to others if you use standard functions (everyone knows the usual behavior fmap
).
a source to share
I will pretend this is homework and not give out the whole answer. If I am wrong, my apologies.
Your type probably Tree
looks something like this:
data Tree a = TreeNode a (Tree a) (Tree a) | EmptyNode
There are two cases here, and you will need to write an implementation mapT
for each of them:
- An inner node,
TreeNode
that carries a type valuea
and has left and right children. What should be done in this case? - Node terminal
EmptyNode
. What should be done in this case?
a source to share
The basic format of the map function applies to both. Let's take a look at the definition of a display function for lists:
map f (x:xs) = f x : map f xs
map _ [] = []
We can summarize it like this:
- You take the first value in the data structure
- Apply a function to it
- Recursively call the display function with the rest of the data structure
- Pass both the modified value and the recursive call to the constructor for your type.
- When you reach the end, stop recursion
All you really need is to look at your constructor and the map function should fall into place.
a source to share
An interesting question if the input and output data are supposed to be sorted by binary trees. If you just naively traverse the tree and use this function, the output tree can no longer be sorted. For example, consider if a function is non-linear, like
f(x) = x * x - 3 * x + 2
If the input has {1, 2, 3, 4}, then the output will have {2, 0, 0, 2}. If the output tree only contains 0 and 2?
If so, you may need to iteratively build the output tree while cutting and processing the input tree.
a source to share