module Unfilled where
import Prelude hiding (Functor(..), Monad(..))
— a great read on functors, monads, and applicatives: https://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html
— from lecture notes:
class Functor f where
fmap :: (a -> b) -> f a -> f b
{-
Functor laws:
Identity: fmap id x == id x
Composition: fmap (f . g) x == fmap f (fmap g x)
-}
class Monad m where
— >>= is pronounced ‘bind’
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
{-
Monad Laws:
Left identity: return a >>= k = k a
Right identity: m >>= return = m
Associativity: m >>= (\x -> k x >>= h) = (m >>= k) >>= h
-}
———————————————
—- TREES —-
———————————————
data Tree a = Tip a | Branch (Tree a) (Tree a)
deriving Show
— TODO: instance Functor Tree where
{-
Functor laws:
Identity: fmap id x == id x
Proof:
Base case:
fmap id (Tip x)
={ … }
id (Tip x)
Induction step: Assume for some left, right : Branch a, the property holds
fmap id (Branch left right)
={ … }
id $ Branch (left) (right)
Composition: fmap (f . g) x == fmap f (fmap g x)
Proof:
Base case:
fmap (f . g) (Tip x)
={ … }
fmap f (fmap g x)
Induction step: Assume for some left, right : Tree a, the property holds
fmap (f . g) (Branch left right)
={ … }
fmap f (fmap g (Branch left right))
-}
— TODO: instance Monad Tree where
{-
Monad Laws:
Left identity: return a >>= k = k a
Proof:
return a >>= k — return
= (Tip a) >>= k — >>=.1
= k a
Right identity: m >>= return = m
Proof by induction:
Base case: m = Tip x
(Tip x) >>= return
={ … }
Tip x
Induction step: Assume property holds for left, right :: Tree a
(Branch left right) >>= return
={ … }
Branch left right
Associativity: m >>= (\x -> k x >>= h) = (m >>= k) >>= h
Proof by induction:
Base case: m = Tip a
(Tip a) >>= (\x -> k x >>= h)
={ … }
((Tip a) >>= k) >>= h
Induction step: Branch left right, assuming the property holds for the left and right
(Branch left right) >>= (\x -> k x >>= h)
={ … }
((Branch left right) >>= k) >>= h
-}
———————————————
—- GTREE —-
———————————————
data GTree a = Leaf a | GNode [GTree a]
deriving Show
— TODO: instance Functor GTree where
— TODO: instance Monad GTree where
———————————————
—- ROSES —-
———————————————
data Rose a = Rose a [Rose a]
deriving Show
— TODO: instance Functor Rose where
— TODO: instance Monad Rose where
———————————————
—- READER —-
———————————————
newtype Reader e a = Reader { runReader :: e -> a }
— TODO: instance Functor (Reader e) where
— TODO: instance Monad (Reader e) where