Haskell : how to use "deriving Show" and functor?

0
votes

Question 1: I have the definition for a tree type:

data Tree a = Node a (Tree a) (Tree a) |Empty

Use the Show typeclass to implement a show function. A tree like Node 10 (Node 20 Empty (Node 6 Empty Empty)) (Node 30 Empty Empty)) should display as (10 (20 x 6) 30) . So, a node with two empty branches should not be parenthesized.

My code is as follows:

data Tree a = Node a (Tree a) (Tree a) |Empty deriving (show) 
 --input
*Main>>Node 10 (Node 20 Empty (Node 6 Empty Empty)) (Node 30 Empty Empty))
 --output
*Main>>Node 10 (Node 20 Empty (Node 6 Empty Empty)) (Node 30 Empty Empty))

Is there any method to change it , let the output is:

(10 (20 x 6) 30)

Question 2:

Use the functor class to define fmap for this type ?
(How can I implement above function use functor?)

2
haskell

2 Answers

2
votes

You can see how to implement Functor instance for Tree here.

If some type is instance of Functor type class it means that you can map it's value and to preserve it's context (use link above to read more about Functor) . For example, if you have tree :: Tree Int with some values in each node, than you can replace all of them by 'A' character using fmap (\ _ -> 'A') tree. The result will be Tree Char, but it is still a Tree.

To print some value, you need to convert it into a String. Converting tree :: Tree a to String produces String but not a Tree Int anymore. That's why you can't use fmap to implement such conversion.

To do that, you have to traverse a Tree a. Only thing you can do just to use fmap is to convert all values to Strings and then concatenate it in some order when traversing a tree.

0
votes

Sure, you would implement Show:

instance Show a => Show (Tree a) where
    show Empty = "()"
    show (Node x Empty Empty) = show x
    show (Node x Empty y) = "(" ++ show x ++ " x " ++ show y ++ ")"
    show (Node x Empty y) = "(" ++ show x ++ " " ++ show y ++ " x)"
    show (Node x y z) = "(" ++ show x ++ " " ++ show y ++ " " ++ show z ++ ")"

However, that would be a bit of an abuse of Show, since it’s supposed to produce output that can reconstruct the input…

http://codepad.org/CDM1v2AY