Typeclassopedia

Ack

Functor

Container

Def

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

Laws

fmap id = id
fmap (g . h) = (fmap g) . (fmap h)

Instances

  • []
  • Maybe
  • Either
  • ((,) e)
  • ((->) e)
  • IO

Applicative

encapsulates certain sorts of “effectful” computations in a functionally pure way, and encourages an “applicative” programming style

Def

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

Laws

-- identity
pure id <*> v = v

-- Homomorphism
pure f <*> pure x = pure (f x)

-- Interchange
u <*> pure y = pure ($ y) <*> u

-- Composition
u <*> (v <*> w) = pure (.) <*> u <*> v <*> w

-- Relate to Functor
fmap g x = pure g <*> x

Considered as left-to-right rewrite rules, the homomorphism, interchange, and composition laws actually constitute an algorithm for transforming any expression using pure and (<>) into a canonical form with only a single use of pure at the very beginning and only left-nested occurrences of (<>). Composition allows reassociating (<*>); interchange allows moving occurrences of pure leftwards; and homomorphism allows collapsing multiple adjacent occurrences of pure into one.

Instances

Most of the standard types which are instances of Functor are also instances of Applicative.

  • Maybe
  • []
  • IO
  • ((,) a)
  • Const
  • WrappedMonad, WrappedArrow

Intuition

Transformation of idealized notation \([[g \, x_1 \, x_2 \, \cdots \, x_n]]\) into haskell, with \(g: t_1 -> t_2 -> \cdots -> t_n\) and \(x_i : f t_i\).

Application falls short if only uses fmap. pure allows embedding “non-effectful” arguments in the middle of an idiomatic application.

g  :: a -> b -> c -> d
x1 :: f a
x2 :: b
x3 :: f c

g <$> x1 <*> pure x2 <*> x3

Alternative formulation1

class Functor f => Monoidal f where
    unit :: f ()
    (**) :: f a -> f b -> f (a,b)
  • left identity
  • right identity
  • associativity
  • naturality

Other Combinators

u *> v = pure (const id) <*> u <*> v
u <* v = pure const <*> u <*> v
(<**>) = flip (<*>)

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

liftA ..

Monad

Def

class Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b
    (>>)   :: m a -> m b -> m b
    m >> n = m >>= \_ -> n
         
    fail   :: String -> m a

Laws

return a >>= k          = k a
m >>= return            = m
m >>= (\x -> k x >>= h) = (m >>= k) >>= h

fmap f xs = xs >>= return . f = liftM f xs


join . fmap join = join . join
join . fmap return = join . return = id
return . f = fmap f . return
join . fmap (fmap f) = fmap f . join

Alternative formulation of the laws are available with (>=>) operator that composes two functions of type a -> m b and b -> m c

Monad Reading List

  • State
  • Reader
  • Writer
  • Cont

Monad Transformers

Combine two monads into one will fail but some monads can be combined into one. Monad transformers can add a particular capability/feature/effect to any existing monad

Standard monad transformers

  • IdentityT
  • StateT
  • ReaderT
  • WriterT
  • RWST
  • MaybeT
  • ErrorT
  • ListT
  • ContT

Def

class MonadTrans t where
    lift :: Monad m => m a -> t m a

Allows arbitrary base monad computations to be “lifted” into computations in the transformed monad t m.

Laws

lift . return = return
lift (m >>= f) = lift m >>= (lift . f)

Transformer type classes and “capability” style

provided by mtl package * use put/get for different monad stack * flexibility to switch between different concrete monad stack

Composing monads

The composition of two monads isn’t always a monad.

join :: m (n (m (n a))) -> m (n a)
-- No general solution, but one situation is if n distribute over m
distrib :: n (m a) -> m (n a)

MonadFix(reading)

Semigroup

Def

set \(S\) together with a binary operator \(\oplus\) which combines elements from \(S\). operator required to be associative.

class Semigroup a where
  (<>) :: a -> a -> a
   
  sconcat :: NonEmpty a -> a
  sconcat = sconcat (a :| as) = go a as where
    go b (c:cs) = b <> go c cs
    go b []     = b
               
  times1p :: Whole n => n -> a -> a
  times1p = ...
  -- Equivalent to sconcat . replicate n

Laws

\((<>)\) must be associative

Monoid

Def

Semigroup plus special element \(e\) for which the binary operation is the identity.

class Monoid a where
  mempty  :: a
  mappend :: a -> a -> a
  -- (<>) is alias for mappend
     
  mconcat :: [a] -> a
  mconcat = foldr mappend mempty

Laws

mempty `mappend` x = x
x `mappend` mempty = x
(x `mappend` y) ` mappend` z = x `mappend` (y `mappend` z)

Instances

Defined in Data.Monoid

  • [a]
  • Sum / Product; for numbers
  • Any / All; for bools
  • First / Last; for maybes
  • Endo a; for a -> a, monoid under composition
  • lift monoid instances to that with additional structure
  • Ordering is monoid, mempty = EQ
  • Map / Set / Sequence
  • Also plays a key role in Foldable
-- Monoid also used to enable several other type class instances. if Monad -> Writer class.
instance Monoid e => Applicative ((,) e) where
  pure x = (mempty, x)
  (u, f) <*> (v, x) = (u `mappend` v, f x)

Other monoidal classes

Alternative, for Applicative functors which also have a monoidal structure. ~ {.haskell} class Applicative f => Alternative f where empty :: f a (<|>) :: f a -> f a -> f a ~

MonadPlus, for Monads ~ {.haskell} class Monad m => MonadPlus m where mzero :: m a mplus :: m a -> m a -> m a – Add “Choice and Failure”, satisfy mzero >>= f = mzero v >> mzero = mzero – mzero denotes failure ~

What is ArrowZero & ArrowPlus?

Foldable

Def

class Foldable t where
  fold    :: Monoid m => t m -> m
  foldMap :: Monoid m => (a -> m) -> t a -> m
   
  foldr   :: (a -> b -> b) -> b -> t a -> b
  foldl   :: (a -> b -> a) -> a -> t b -> a
  foldr1  :: (a -> a -> a) -> t a -> a
  foldl1  :: (a -> a -> a) -> t a -> a

  -- Only foldMap or foldr needs to be provided

Instances

Containers: [], Tree, Maybe, Array, Map, Set, Tree, Sequence

Derived folds

using foldMap to compute the size of container or compute a list of elements satisfying a predicate…

Foldable actually isn’t

fold summarize only one level of structure where as Catamorphism2 can summarize an entire recursive structure.

Foldable allows only the left-right order of elements within a structure not the actual structure. => every use of Foldable -> in terms of toList3

Traversable

Def

class (Functor t, Foldable t) => Traversable t where
  traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)
  mapM      ::       Monad m => (a -> m b) -> t a -> m (t b)
  sequence  ::       Monad m => t (m a) -> m (t a)
  -- Note that every monad is also applicative
  -- And any Traversable is also Functor and Foldable

Intuition: view Traversable as a generalization of Functor. Traverse is an “effectful fmap”.

Traversable and Functor instances for any type is almost identical: normal function application v.s. (<$>) (<>)* in Applicative context

  • []
  • Maybe
  • Map
  • Tree
  • Sequence

Laws

traverse Identity = Identity
-- Data.Functor.Identity
-- No arbitrary effects
traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f
-- Data.Functor.Compose (Composition of two functors)
-- How two traverse can be collapsed into one

Category

Def

Generalize the notion of function composition into general “morphisms”

class Category cat where
  id  :: cat a a
  (.) :: cat b c -> cat a b -> cat a c
  -- kind: Category :: * -> * -> *
  -- (->) as Category

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }
 
instance Monad m => Category (Kleisli m) where
  id = Kleisli return
  Kleisli g . Kleisli h = Kleisli (h >=> g)

Laws

  • id is the identity of (.)
  • (.) is associative

Arrow

Def

class Category arr => Arrow arr where
  arr :: (b -> c) -> (b `arr` c)
  first :: (b `arr` c) -> ((b, d) `arr` (c, d))
  second :: (b `arr` c) -> ((d, b) `arr` (d, c))
  (***) :: (b `arr` c) -> (b' `arr` c') -> ((b, b') `arr` (c, c'))
  (&&&) :: (b `arr` c) -> (b `arr` c') -> (b `arr` (c, c'))
  -- Category -> id & composition
  -- arr & first needs to be defined

Intuition

  • arr takes any function b -> c and turns it into a generalized arrow b arr c.
  • first turns any arrow from b to c into an arrow from (b,d) to (c,d)
  • second defined by swap let arr a b = first f in arr (swap a) (swap b)
  • (**)* parallel composition of arrows
  • (&&&) fanout composition of arrows

Instances

  • (->)
  • Kleisli turns any function of type a -> m b into arrow for any Monad m

Laws4

arr id  =  id
arr (h . g)  =  arr g >>> arr h
first (arr g)  =  arr (g *** id)
first (g >>> h)  =  first g >>> first h
first g >>> arr (id *** h)  =  arr (id *** h) >>> first g
first g >>> arr fst  =  arr fst >>> g
first (first g) >>> arr assoc  =  arr assoc >>> first g
-- assoc ((x,y),z) = (x,(y,z))

ArrowChoice

Provide the ability to choose among a finite number of predefined execution paths based on the intermediate results.

class Arrow arr => ArrowChoice arr where
  left  :: (b `arr` c) -> (Either b d `arr` Either c d)
  right :: (b `arr` c) -> (Either d b `arr` Either d c)
  (+++) :: (b `arr` c) -> (b' `arr` c') -> (Either b b' `arr` Either c c')
  (|||) :: (b `arr` d) -> (c `arr` d) -> (Either b c `arr` d)
  • left and right resembles that of 1st & 2nd
  • (+++) “multiplexing”
  • (|||) “fanin”

ArrowApply

Allows to compute an arrow from intermediate results, and use this computed arrow to continue the computation.

class Arrow arr => ArrowApply arr where
  app :: (b `arr` c, b) `arr` c

Define instance for Kleisli

ArrowLoop

Describes arrows that can use recursion to compute results, and to desugar the rec construct in arrow notation.

class Arrow a => ArrowLoop a where
  loop :: a (b, d) (c, d) -> a b c
   
trace :: ((b,d) -> (c,d)) -> b -> c
trace f b = let (c,d) = f (b,d) in c

loop is a generalization of the trace function. laziness at work for g.

Arrow notation

Allows names to be assigned to intermediate results.

Paterson’s paper

Comonad

Categorical dual of Monad, with all the function arrows flipped.

class Functor w => Comonad w where
  extract :: w a -> a
   
  duplicate :: w a -> w (w a)
  duplicate = extend id
       
  extend :: (w a -> b) -> w a -> w b
  extend f = fmap f . duplicate

  1. How did it come about? Ex2,Ex3↩

  2. wiki; haskwiki↩

  3. depth of tree can be implemented with Catamorphism but not Foldable↩

  4. Consult Paterson: Programming with Arrows↩