Author : Kenta Inoue

Introduction

This page describes Functor, Applicative and Monad, which are typeclasses in functional languages. These are typeclasses that take one type as an argument and have a wide range of uses, such as making error handling easier by applying them. This article summarizes the features of Functor and others.

First, we will discuss types that take types as arguments.

Types that take a type as an argument

Types that take a type as an argument include List and Maybe/Option types for single-argument types, and Direct Sum and Direct Product types for multi-argument types. In the case of multiple-argument types, they can be regarded as a single argument if they are curried, so this article considers single-argument types as types that take a single argument as an argument.

Let m be a type that takes one argument. For any type A, m A is a type, but often it is something that can be related to the original type A. For example, if m is a Maybe/Option, a direct sum, etc., then there exists a (canonical) injection of A -> m A, and m A can be thought of as containing A, i.e. A ⊂ m A.

Using this relationship between types A and m A, Usually, we can canonically define a function that takes arguments of type m A from a function f that takes arguments of type A. For example, when m is Maybe, the function returns Just (f x) if the input is Just x, and returns Nothing if it is Nothing.

Functor, Applicative, and Monad make it easy to use functions that takem Atype arguments, which are naturally defined from functions that take suchA type arguments.

Let's take a look at the features of each.

Functor

Functor is a typeslass that can convert m A -> m B functions from A -> B functions for arbitrary types A and B, as opposed to type m which takes one argument.

In fact, in haskell, the Functor typeclass is defined from fmap :: (a -> b) -> a -> b as the following.

class functor f where
            fmap :: (a -> b) -> f a -> f b
        
        (<$>) :: Functor f => (a -> b) -> f a -> f b
        (<$>) = fmap

Actually (<$>) f for f::A -> B has type m A -> m B. For example, if m is of type Maybe, then f <$> Just x returns Just (f x) and f <$> Nothing returns Nothing, as described above.

Axioms required for Functor

For a type m that takes a type as an argument, Functor m must satisfy the following axioms.

• For any types A, B, C and functions f::A -> B, g::B -> C, and x::m A. g . f <$> x ＝ g <$> (f <$> x)
• For any type A, x::m A. id <$> x ＝ x

The first axiom states that the following commutative diagram holds.

The second axiom concerns the identity projection.

Examples of Functor

We will look at the implementation of haskell.

Maybe type

instance Functor Maybe where
            fmap _ Nothing = Nothing
            fmap f (Just a) = Just (f a)

Either (direct sum) type

instance Functor (Either a) where
            fmap _ (Left x) = Left x
            fmap f (Right y) = Right (f y)

[] (list) type

instance Functor [] where
           fmap = map

(,) (direct product) type

instance Functor ((,) a) where
           fmap f (x,y) = (x,f y)

Applicative

The main use of Applicative is to convert functions of type m A -> m B -> m C. from multi-argument functions such as A -> B -> C for arbitrary types A, B, C, etc.

This cannot be achieved with just a Functor type class, so another type class Applicative is needed. Let's look at the actual definition.

class Functor f => Applicative f where
            pure :: a -> f a
        
            (<*>) :: f (a -> b) -> f a -> f b
            (<*>) = liftA2 id
        
            liftA2 :: (a -> b -> c) -> f a -> f b -> f c
            liftA2 f x = (<*>) (fmap f x)

(<*>) and liftA2 are mutually defined, so that if one is given, the other is automatically defined.

liftA2 has two arguments, but we can define it for more than two arguments.

liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d
        liftA3 f a b c = liftA2 f a b <*> c

Axioms required for Applicative

For any type m that takes a type as an argument, Applicative m is needed to satisfy the following axioms

• For any type A, v::m A, pure id <*> v ＝ v
• For any type A, B, C, D, f::m (B -> C), g::m (A -> B), x::m A, pure (.) <*> f <*> g <*> x ＝ f <*> (g <*> x)
• For any type A, B, f::A -> B, x::A, pure f <*> pure x ＝ pure (f x)
• For any type A, B, f::m (A -> B), x::A, f <*> pure x ＝ pure ($ x) <*> f

The first axiom shows that a Functor can be made from an Applicative. In fact, for any type A, B, f:A -> B and x:m A, we can define f <$> x as pure f <*> x, then the axiom is exactly the same of it in Functor. Another axiom of Functor can be proved by the second and third axioms of Applicative.

The second axiom is a bit confusing, but if you rewrite it using liftA3, you will see that it expresses the following associative law. liftA3 (.) f g x ＝ f <*> (g <*> x)

The third axiom is not an Applicative law, but rather represents the following commutative diagram of pure and <$>.

The last axiom shows the changes of operands.

Examples of Applicative

Maybe type

instance Applicative Maybe where
            pure = Just
        
            Just f <*> m = fmap f m
            Nothing <*> _m = Nothing

Either (direct sum) type

instance Applicative (Either e) where
            pure = Right
            Left e <*> _ = Left e
            Right f <*> r = fmap f r

[] (list) type

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

Although this is the definition in the library, the Applicative rule actually holds in the following definition.

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

This definition generally produces a different output for <*>, but it does not satisfy the specification for making Monad as described below.

(,) direct product type

instance Monoid a => Applicative ((,) a) where
            pure x = (mempty, x)
            (u, f) <*> (v, x) = (u <> v, f x)

The type a must be a monoid, using the unitary source mempty and the operation <>.

Monad

Monad is a typeclass that can convert m A -> m B from A -> m B for arbitrary types A and B. Since this cannot be made from Applicative and Functor, the following typeclasses are used.

class Applicative m => Monad m where
        
            (>>=) :: forall a b. m a -> (a -> m b) -> m b
        
            return :: a -> m a
            return = pure

Although Monad inherits from Applicative, note that there are actually multiple ways to create an Applicative from Monad.

Note on Applicative inheritance.

If given Monad m, we can define the following two Applicatives from this m.

class Monad m => VApplicative m where
          vpure :: a -> m a
          vpure = pure
        
          (<*.>) :: m (a -> b) -> m a -> m b  
          f <*.> x = f >>= (<$> x)
        
        class Monad m => HApplicative m where
          hpure :: a -> m a
          hpure = pure
        
          (<*..>) :: m (a -> b) -> m a -> m b  
          f <*..> x = x >>= \y -> ($ y) <$> f

Furthermore, the two generally differ in their execution results.

instance VApplicative [] where
        instance HApplicative [] where
        
        fs :: [Int -> Int]
        fs = [\n -> n + 1,\n -> n + 2]
        
        ns :: [Int]
        ns = [30,40]
        
        main :: IO ()
        main = do
          print $ fs <*> ns   -- [31,41,32,42]
        
          print $ fs <*.> ns  -- [31,41,32,42]
          print $ fs <*..> ns -- [31,32,41,42]

These are two, but in haskell they are needed to be the former definition (or more precisely f <*> x ＝ f >>= (\y -> x >>= \z -> return (y z))).

With this in mind, we will review the following axioms for Monad.

Axioms required for Monad.

For a type m that takes a type as an argument, Monad m must satisfy the following axioms.

• For any types A, B, any x::A, f::A -> m B, return x >>= f ＝ f x
• For any type A, any x::m A, x >>= return ＝ x
• x >>= f >>= g for any type A, B, C, any x::m A, f::A -> m B, g::B -> m C ＝ x >>= (\y -> f y >>= g)

The first and seconds are properties about return of passing >>= left and right, respectively. The third one is related to the associative law of >>=.

Examples of Monad

Maybe type

instance Monad Maybe where
            (Just x) >>= k = k x
            Nothing >>= _ = Nothing

Either (direct sum) type

instance Monad (Either e) where
            Left l >>= _ = Left l
            Right r >>= k = k r

[] list type

instance Monad [] where
            xs >>= f = [y | x <- xs, y <- f x]

(,) direct product type

instance Monoid a => Monad ((,) a) where
            (u,a) >>= k = case k a of (v,b) -> (u <> v,b)

The type a must be monoidal and uses the operation <>.

Summary

We have summarized the features of Functor, Applicative and Monad. These three can be briefly summarized as follows.

• Functor m : convert m A -> m B from A -> B.
• Applicative m : convert m A -> m B -> m C from A -> B -> C.
• Monad m : convert m A -> m B from A -> m B. (for any type A, B, C)

Since Monad inherits from the above two, we can use all of these in Monad. We can use functions of the original world in the world of type m that returns a type using these.