Haskell Notes

haskell-notes.org

Functors

Definition

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

Laws

fmap id = id
≡ 
id

fmap (f . g) F 
≡ 
fmap f (fmap g F) -- for any Functor F

Applicative Functors

Definition

class (Functor f) => Applicative f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

(<$>) :: (Functor f) => (a -> b) -> f a -> f b
f <$> x = fmap f x

Laws

pure f <*> x 
≡ 
fmap f x 

pure id <*> v
≡ 
v

pure (.) <*> u <*> v <*> w 
≡ 
u <*> (v <*> w)

pure f <*> pure x 
≡ 
pure (f x)

u <*> pure y 
≡ 
pure ($ y) <*> u

Monoids

Definition

class Monoid m where
  mempty :: m
  mappend :: m -> m -> m
  mconcat :: [m] -> m
  mconcat = foldr mappend mempty

Laws

mappend mempty x
≡ 
x

mappend x mempty
≡ 
x

mappend (mappend x y) z 
≡ 
mappend x (mappend y z)

Monads

Definition

class Monad m where
  return :: a -> m a

  (>>=) :: m a -> (a -> m b) -> m b

  (>>) :: m a -> m b -> m b
  x >> y = x >>= \_ -> y

  fail :: String -> m a
  fail msg = error msg

Laws

Left Identity

return x >>= f
≡ 
f x

Right Identity

m >>= return
≡ 
m

Associativity

(m >>= f) >>= g
≡ 
m >>= (\x -> f x >>= g)

Example: Sequence

module Sequence (
  mc,
  sequ
) where

sequ :: Monad m => [m a] -> m [a]
sequ = foldr mc (return [])

mc :: Monad m => m t -> m [t] -> m [t]
mc p q = do
  x <- p
  y <- q
  return (x:y)

Sequence list of Maybe and collect results, if successful

sequence [Just 3, Just 4]          -- Just [3,4]
sequence [Just 3, Just 4, Nothing] -- Nothing

Generate Cartesian Product of

sequence [[1,2,3],[4,5]] -- [[1,4],[1,5],[2,4],[2,5],[3,4],[3,5]]

Do Notation

Desugaring Rules

do { a <- f ; m } 
≡ 
f >>= \a -> do { m }

do { f ; m } 
≡ 
f >>= \a -> do { m }

do { m } 
≡ 
m

Laws

Law 1

do x <- m 
   return x
≡ 
do m

Law 2

do y <- return x 
   f y
≡ 
do f x

Law 3

do b <- do a <- m 
           f a 
   g b 
≡ 
do a <- m 
   b <- f a 
   g b }
≡ 
do a <- m
   do b <- f a
      g b

Reader Monad

Definition

The Reader Monad lets us access shared immutable state within a monadic context.

ask :: Reader r a
asks :: (r -> a) -> Reader r a
local :: (r -> b) -> Reader b a -> Reader r a
runReader :: Reader r a -> r -> a

Example

import Control.Monad.Reader

data MyContext = MyContext
  { foo :: String
  , bar :: Int
  } deriving (Show)

computation :: Reader MyContext (Maybe String)
computation = do
  n <- asks bar
  x <- asks foo
  if n > 0
    then return (Just x)
    else return Nothing

ex1 :: Maybe String
ex1 = runReader computation $ MyContext "hello" 1

ex2 :: Maybe String
ex2 = runReader computation $ MyContext "haskell" 0

Implementation

newtype Reader r a = Reader { runReader :: r -> a }

instance Monad (Reader r) where
  return a = Reader $ \_ -> a
  m >>= k  = Reader $ \r -> runReader (k (runReader m r)) r

ask :: Reader a a
ask = Reader id

asks :: (r -> a) -> Reader r a
asks f = Reader f

local :: (r -> b) -> Reader b a -> Reader r a
local f m = Reader $ runReader m . f

Writer Monad

Definition

The writer monad lets us emit a lazy stream of values from within a monadic context.

tell :: w -> Writer w ()
execWriter :: Writer w a -> w
runWriter :: Writer w a -> (a, w)

Example

import Control.Monad.Writer

type MyWriter = Writer [Int] String

example :: MyWriter
example = do
  tell [1..5]
  tell [5..10]
  return "foo"

output :: (String, [Int])
output = runWriter example

Implementation

import Data.Monoid

newtype Writer w a = Writer { runWriter :: (a, w) }

instance Monoid w => Monad (Writer w) where
  return a = Writer (a, mempty)
  m >>= k  = Writer $ let
                        (a, w)   = runWriter m
                        (b, w')  = runWriter (k a)
                      in (b, mappend w w')

  execWriter :: Writer w a -> w
  execWriter m = snd (runWriter m)

  tell :: w -> Writer w ()
  tell w = Writer ((), w)

State Monad

Definition

The State Monad sllows functions within a stateful monadic context to access and modify shared state. Note: the state monad is pure.

runState  :: State s a -> s -> (a, s)
evalState :: State s a -> s -> a
execState :: State s a -> s -> s

Example

import Control.Monad.State

test :: State Int Int 
test = do
  put 3
  modify (+ 1)
  get 

main :: IO ()
main = print $ execState test 0

Implementation

newtype State s a = State { runState :: s -> (a,s) }

instance Monad (State s) where
  return a = State $ \s -> (a, s)
  
  State act >>= k = State $ \s ->
    let (a, s') = act s
    in runState (k a) s'

get :: State s s
get = State $ \s -> (s, s)

put :: s -> State s ()
put s = State $ \_ -> ((), s)

modify :: (s -> s) -> State s ()
modify f = get >>= \x -> put (f x)

evalState :: State s a -> s -> a
evalState act = fst . runState act 

execState :: State s a -> s -> s
execState act = snd . runState act