-- Examples of functors (and not) and applicatives
-- Venanzio Capretta, February 2016
-- Pairs of elements of type a
newtype Pair a = Pair (a,a)
deriving (Eq,Ord,Show,Read)
instance Functor Pair where
fmap f (Pair (x,y)) = Pair (f x, f y)
-- But we can't make an instance of Applicatvie for Pair.
-- Try it and understand why.
-------------------------------------
-- Node Trees: trees with data on the nodes
data NTree a = NLeaf | NNode a (NTree a) (NTree a)
deriving (Eq,Ord,Show,Read)
instance Functor NTree where
fmap f NLeaf = NLeaf
fmap f (NNode x left right) = NNode (f x) (fmap f left) (fmap f right)
-- What about Applicative?
-- Is it possible to define and instance of Applicative for NTree?
-------------------------------------
-- Leaf Trees: trees with data on the leaves
data LTree a = LLeaf a | LNode (LTree a) (LTree a)
deriving (Eq,Ord,Show,Read)
instance Functor LTree where
fmap f (LLeaf x) = LLeaf (f x)
fmap f (LNode left right) = LNode (fmap f left) (fmap f right)
instance Applicative LTree where
pure = LLeaf
LLeaf f <*> xs = fmap f xs
LNode left right <*> xs = LNode (left <*> xs) (right <*> xs)
-------------------------------------
-- Finitely branching trees (with data on the nodes and leaves)
data FTree a = FNode a [FTree a]
deriving (Eq,Ord,Show,Read)
instance Functor FTree where
fmap f (FNode x ts) = FNode (f x) (map (fmap f) ts)
-- Applicative?
-------------------------------------
-- a-branching trees
-- NOT a functor
data ATree a = ALeaf | ANode (a -> ATree a)
-- It's impossible to define an instance of Functor for ATree
-- Think about why this is not a functor
-------------------------------------
-- FIFO lists (first in first out)
data Queue a = Queue [a] [a]
deriving (Eq,Ord,Show,Read)
-- Think of a pair of lists (Queue [x0,..,xn] [y0,..,ym])
-- as a single queue x0,..,xn,ym,..y0
-- Elements are pushed in front and popped from the end
emptyQ :: Queue a
emptyQ = Queue [] []
push :: a -> Queue a -> Queue a
push x (Queue xs ys) = Queue (x:xs) ys
pop :: Queue a -> (Maybe a, Queue a)
pop (Queue [] []) = (Nothing, emptyQ)
pop (Queue xs (y:ys)) = (Just y, Queue xs ys)
pop (Queue xs []) = pop (Queue [] (reverse xs))
instance Functor Queue where
fmap g (Queue xs ys) = Queue (fmap g xs) (fmap g ys)
-- Exercise: make an instance of Applicative for Queue
-------------------------------------
-- Wrong fmap for lists
newtype MList a = MList [a]
deriving (Eq,Ord,Show,Read)
app :: MList a -> MList a -> MList a
app (MList xs) (MList ys) = MList (xs ++ ys)
instance Functor MList where
fmap g (MList []) = MList []
fmap g (MList (x:xs)) = fmap g (MList xs) `app` (MList [g x])
-- This definition doesn't satisfy the functor laws
-------------------------------------
-- IO is also a functor, the instance is defined in the Prelude
readInt :: IO Int
readInt = putStrLn "Write a number: " >> readLn
-- Try to run first readInt, then fmap (+13) readInt
-- IO is also an applicative
-- Try: (\x y z -> (x+y)*z) <$> readInt <*> readInt <*> readInt