Applicative Functors

Kinds

  • For the compiler to accept a program, it must be well typed
  • Kinds are the "types of types"
  • Types are denoted with expression :: type
    • eg True :: Bool
  • Kinds are denoted the same: type :: kind
    • Bool :: *
  • The compiler infers kinds of types the same way it infers types of expressions
  • * is the kind of types
  • Bool :: * because Bool has no type parameters
    • data Bool = True | False
  • Maybe is parametrised over some type a, so the kind signature Maybe :: * -> * means that if given a type as an argument to the type constructor Just, it will give back some other type of kind *
  • [] :: * -> *
    • [] is the type constructor for lists

Kinds are important when defining typeclasses. Take Functor, for example:

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

This definition shows that the type f is applied to one argument (f a), so f :: * -> *

-- Maybe :: * -> *
instance Functor Maybe where
  fmap f Nothing = Nothing
  fmap f (Just x) = Just (f x)

-- invalid
-- Maybe a :: *
-- As the type is already applied to a
instance Functor (Maybe a) where
  fmap f Nothing = Nothing
  fmap f (Just x) = Just (f x)

The Either Type

Either is usually used to represent the result of a computation when it could give one of two results. Right is used to represent success, and a is the wanted value. Left is used to represent error, with e as some error code/message.

data Either e a = Left e | Right a
Left :: e -> Either e a
Right :: a -> Either e a

Either has kind * -> * -> *, as it must be applied to two types e and a before we get some other type.

Only types of kind * -> * can be functors, so we need to apply Either to one argument first. The functor instance for Either applies the function to the Right value.

instance Functor (Either e) where
  fmap :: (a -> b) -> Either e a -> Either e b
  fmap f (Left x)  = Left x
  fmap f (Right y) = Right (f y)

The Unit Type ()

  • () is called the unit type
  • () :: ()
    • (), the unit value, has type ()
    • () is the only value of type ()
  • Can be thought of as defined data () = ()
  • Or an empty tuple

Semigroups and Monoids

A type is a semigroup if it has some associative binary operation defined on it. This operator (<>) is the "combine" operator.

class Semigroup a where
  (<>) :: a -> a -> a

instance Semigroup [a] where
  -- (<>) :: [a] -> [a] -> [a]
  (<>) = (++)

instance Semigroup Int where
  -- (<>) :: Int -> Int -> Int
  (<>) = (+)

A type is a monoid if it is a semigroup that also has some identity value, called mempty:

class Semigroup a => Monoid a where
  mempty ::a

instance Monoid [a] where
  -- mempty :: [a]
  mempty = []

instance Monoid Int where
  -- mempty :: Int
  mempty = 0

Applicatives

Applicative Functors are similar to normal functors, except with a slightly different type definition:

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

The typeclass defines two functions:

  • pure just lifts the value a into the "box"
  • <*> (the apply operator) takes some function (a -> b) in a box f, and applies it to a value a in a box, returning the result in the same box.
    • "box" is a rather loose analogy. It is more accurate to say "computational context".

Different contexts for function application:

-- vanilla function application
(\$) :: (a -> b) -> a -> b
-- Functor's fmap
(<\$>) :: Functor f => (a -> b) -> f a -> f b
-- Applicative's apply
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

Maybe and Either e are both applicative functors:

instance Applicative Maybe where
  pure x = Just x
  Nothing <*> _ = Nothing
  (Just f) <*> x = f <\$> x

instance Applicative (Either e) where
  pure = Right
  Left err <*> _ = Left err
  Right f  <*> x = f <\$> x

The "context" of both of these types is that they represent error. All data flow in haskell has to be explicit due to its purity, so these types allow for the propagation of error.

Another example of an applicative functor is a list:

instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs]

Every function in the left list is applied to every function in the right:

[f, g] <*> [x, y, z]
=> [f x, f y, f z, g x, g y, g z]

g <\$> [x,y] <*> [a,b,c]
=> [g x, g y] <*> [a,b,c]
=> [g x a, g x b, g x c, g y a, g y b, g y c]

The context represented by lists is nondeterminism, ie a function f given one of the arguments [x, y, z] could have result [f x, f y, f z].

Applicative Laws

Applicative functors, like normal functors, also have to obey certain laws:

  • pure id <*> x = x
    • The identity law
    • applying pure id does nothing
  • pure f <*> pure x = pure (f x)
    • Homomorphism
    • pure preserves function application
  • u <*> pure y = pure (\$ y) <*> u
    • Interchange
    • Applying something to a pure value is the same as applying pure ($ y) to that thing
  • pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
    • Composition
    • Function composition with (.) works within a pure context.

Left and Right Apply

<* and *> are two more operators, both defined automatically when <*> is defined.

const :: a -> b -> a
const x y = x

flip :: (a -> b -> c) -> b -> a -> c
flip f x y = f y x

(<*) :: Applicative f => f a -> f b -> f a
a0 <* a1 = const <\$> a0 <*> a1

(*>) :: Applicative f => f a -> f b -> f b
a0 *> a1 = flip const <\$> a0 <*> a1

In simple terms *> is used for sequencing actions, discarding the result of the first argument. <* is the same, except discarding the result of the second.

Just 4 <* Just 8
=> const <\$> Just 4 <*> Just 8
=> Just (const 4) <*> Just 8
=> Just (const 4 8)
=> Just 4

Just 4 <* Nothing
=> const <\$> Just 4 <*> Nothing
=> Just (const 4) <*> Nothing
=> Nothing

Just 4 *> Just 8
=> flip const <\$> Just 4 <*> Just 8
=> Just (flip const 4) <*> Just 8
=> Just (flip const 4 8)
=> Just (const 8 4)
=> Just 8

Nothing *> Just 8
=> Nothing

These operators are perhaps easier to understand in terms of monadic actions:

as *> bs = do as
              bs
as *> bs = as >> bs

as <* bs = do a <- as
              bs
              pure a

Example: Logging

A good example to illustrate the uses of applicative functors is logging the output of a compiler. If we have a function comp that takes some Expr type, representing compiler input, and returns some Program type, representing output :

comp :: Expr -> Program
comp (Val n) = [PUSH n]
comp (Plus l r) = comp l ++ comp r ++ [ADD]
-- extending to return a String for a log
comp :: Expr -> (Program, [String])
comp (val n) = ([PUSH n],["compiling a value"])
comp (Plus l r) = (pl ++ pr ++ [ADD], "compiling a plus" : (ml ++ mr))
  where (pl, ml) = comp l
        (pr, mr) = comp r

This is messy and not very clear what is going on. There is a much nicer way to do this, using the Writer type:

-- w is the "log"
-- a is the containing type (the type in the "box")
data Writer w a = MkWriter (a,w)
--type of MkWriter
MkWriter :: (a,w) -> Writer w a
-- kind of Writer type
Writer :: * -> * -> *

instance Functor (Writer w) where
  -- fmap :: (a -> b) -> Writer w a -> Writer w b
  fmap f (MkWriter (x,o)) = MkWriter (f x, o) -- applies the function to the x value

-- a function to write a log
-- generates a new writer with a msg and unit type in it's box
writeLog :: String -> Writer [w] ()
writeLog msg = MkWriter((), [msg])

Using this to redefine comp:

comp :: Expr -> Writer [String] Program
comp (Val n) = MkWriter ([PUSH n], m)
  where (MkWriter (_, m)) = writeLog "compiling a value"
comp (Plus l r) = MkWriter (pl ++ pr ++ [ADD], m ++ ml ++ mr)
  where (MkWriter (pl, ml)) = comp l
        (MkWriter (pr, mr)) = comp r
        (MkWriter (_, m))   = writeLog

This definition of comp combines the output using Writer, but is messy as it uses pattern matching to deconstruct the results of the recursive calls and then rebuild them into the result. It would be nice if there was some way to implicitly keep track of the log messages.

We can define an instance of the Applicative typeclass for Writer to do this. There is the additional constraint that w must be an instance of Monoid, because we need some way to combine the output of the log.

instance Monoid w => Applicative (Writer w) where
  --pure :: a -> Writer w a
  pure x = MkWriter (x, mempty)
  -- <*> Monoid w => Writer w (a -> b) -> Writer w a -> Writer w b
  MkWriter (f,o1) <*> MkWriter (x,o2) = MkWriter (f x, o1 <> o2)
  -- f is applied to x, and o1 and o2 are combined using their monoid instance

Using this definition, the comp function can be tidied up nicely using <*>

comp :: Expr -> Writer [String] Program
comp (Val n) = writeLog "compiling a value" *> pure [PUSH n]
comp (Plus l r) = writeLog "compiling a plus" *>
    ((\p p' -> p ++ p' ++ [ADD]) <\$> comp l <*> comp r)

The first pattern uses *>. Recall that *> does not care about the left result, which in this case is the unit type, so only the result of the right Writer is used, which is the [PUSH n] put into a Writer by pure, with a mempty, or [] as the logged value.

The second pattern applies the anonymous function (\p p' -> p ++ p' ++ [ADD]) to the result of the recursive calls. The lambda defines how the results of the recursive calls are combined together, and the log messages are automatically combined by the definition of <*>. *> is used again to add a log message to the program.