import Prelude hiding (map, Functor, fmap)

-- Apply a function to every element in a list:
map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = (f x) : map f xs

-- Binary trees:
data Tree a = Leaf a | Node (Tree a) (Tree a)
 deriving Show

t123 :: Tree Int
t123 = Node (Leaf 1) (Node (Leaf 2) (Leaf 3))

-- Apply a function to every element in a tree:
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f (Leaf x)     = Leaf (f x)
mapTree f (Node t1 t2) = Node (mapTree f t1) (mapTree f t2)

-- Apply a function to a Maybe container:
mapMaybe :: (a -> b) -> Maybe a -> Maybe b
mapMaybe f Nothing  = Nothing
mapMaybe f (Just x) = Just (f x)

-- Generalization in a type constructor class:
class Functor tc where  -- tc is some type constructor
  fmap :: (a -> b) -> tc a -> tc b

instance Functor [] where -- [] is the type constructor for lists: data [] a = ...
  fmap = map

instance Functor Tree where
  fmap = mapTree

instance Functor Maybe where
  fmap = mapMaybe

-- Application: an increment function on all elements in some container:
incAll :: Functor tc => tc Int -> tc Int
incAll = fmap (+1)

-- An instance for IO:
instance Functor IO where
  fmap f act = do x <- act
                  return (f x)

getLineLength :: IO Int
getLineLength = fmap length getLine

getNonBlanks :: IO String
getNonBlanks = fmap (filter (/=' ')) getLine

{-
Laws of the Functor class:

fmap id      = id               -- identity law
fmap (f . g) = fmap f . fmap g  -- composition law


-- This does not satisfy the identity law:
instance Functor [] where
  fmap f []     = []
  fmap f (x:xs) = fmap f xs ++ [f x]

-}