CODEWITHSUNDEEP
haskell
RM777
RM777

Reputation: 203

Maps on Trees in Haskell

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?

Upvotes: 3

Views: 1143

Answers (1)

castletheperson
castletheperson

Reputation: 33476

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

Upvotes: 12

Related Questions