Maps on Trees in Haskell

Question

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

map :: (a -> b) -> [a] -> [b]

How can I define a function that operates like map but works on trees? The typesignature of the new funtion would be:

mapTree :: (a -> b) -> Tree a -> Tree b

Is it even possible to create a generic typeclass for map?

Answer 1

That typeclass already exists in Prelude: Functor.

class Functor f where
    fmap :: (a -> b) -> f a -> f b

To implement it, you could use the DeriveFunctor language extension so that GHC can implement it for you with just a deriving clause:

{-# LANGUAGE DeriveFunctor #-}

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

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree = fmap

Or you can implement it manually:

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

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree _ Empty = Empty
mapTree f (Node x l r) = Node (f x) (mapTree f l) (mapTree f r)

instance Functor Tree where
    fmap = mapTree