Functors and Applicative Functors

__functors.md

What's a Functor?

A functor is a type class that is used for types that can be mapped over.

What's it mean to "map over" something?

Map Over a List

mapList :: (a -> b) -> [a] -> [b]
mapList g [] = []
mapList g (x:xs) = (g x) : (map g xs)

In the above example, we're mapping the function g over a list of a to produce a list of b.

Map Over a Tree

data Tree a = Empty | Node (Tree a) a (Tree a) deriving (Show, Eq)

mapTree :: (a -> b) -> Tree a -> Tree b
mapTree g Empty = Empty
mapTree g (Node t1 v t2) = Node (mapTree g t1) (f v) (mapTree g t2)

In this scenario, we're mapping the function g over a Tree a to produce a Tree b.

Map Over a Maybe

data Maybe a = Nothing | Just a deriving (Show, Eq)

mapMaybe :: (a -> b) -> Maybe a -> Maybe b
mapMaybe g Nothing = Nothing
mapMaybe g (Just x) -> Just g x

In this scenario, we're mapping the function g over a Maybe a to produce a Maybe b.

Generalizing

So, we'd like to generalize this concept of mapping a function a -> b over Maybe a, Tree a and [a] - but what do they have in common?

Kinds

Every type in Haskell has a kind, which is sort of like a type-of-types. Using GHCI, we can figure out what the kind of a type is:

Prelude> :k Int
Int :: *

Prelude> :k Maybe
Maybe :: * -> *

The kind * -> * is - as per the lecture can be thought of as a "function on types."

Example: The kind of Maybe is * -> *. The function on types is awaiting a type of kind * and will then produce a new type of kind *. Int is of kind *; Maybe Int is of kind *, too. We can partially apply these types like we would functions, too.

data Foo a b c = Foo a b c

Prelude> :k Foo
Foo :: * -> * -> * -> *

Prelude> :k Foo Int Char
Foo Int Char :: * -> *

Note that the number of type variables doesn't dictate a type's kind:

data Bar a b = Bar (a b) b

Prelude> :k Bar
Bar :: (* -> *) -> * -> *

Bar is a type that is parameterized by two type variables: a, which is itself a type which is parameterized by a type b (of kind * -> *) and then b (of kind *). Thus it's kind is (* -> *) -> * -> *.

Back to Generalizing

So, what do Tree a and Just a and Maybe a all have in common? They're all of kind * -> *. We can use this to separate the application of our function a -> b from the magical context (e.g. Tree a or Maybe a or whatever) that holds our a.

The Functor Type Class

Lo! The Functor type class:

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

The Functor type class can be instantiated by any type f that is itself parameterized by one other type a.

It's one required member, fmap can be described as "give me a mapping function a -> b and a value of a type which is parameterized by a and I'll give you back a new value of a type which is parameterized by b." Let's see one in action:

instance Functor (Tree a) where
  fmap f Empty = Empty
  fmap f (Node t1 v t2) = Node (fmap f t1) (f v) (fmap f t2)

or for Maybe a:

instance Functor [a] where
  fmap f [] = []
  fmap f (x:xs) = (f x) : (fmap f xs)

We've taking our mapTree and mapMaybe functions from above and moved them into type class instances of Functor, which allows us to write code that's functor agnostic, e.g.

valuesToInt :: Functor f => f String -> f Int
valuesToInt fs = fmap read fs

...which can be used with Tree or Maybe or List:

valuesToInt ["1", "200", "12"] // [1, 200, 12]
valuesToInt (Just "123") // Just 123
valuesToInt (Node (Node (Node Empty '30' Empty) '2' Empty) '1' Empty) // (Node (Node (Node Empty 30 Empty) 2 Empty) 1 Empty)

A Mind-Bender

A function of a type a -> b -> c is a function of kind * -> * -> *. We know that we can partially apply kinds, which means that for any type of kind * -> * -> * partially applied to a kind of type *, we have the kind of Functor. The implication here is that a partially-applied binary function itself is a unctor`:

instance Functor ((->) e) where
  fmap f g = f . g // because f :: a -> b and g :: e -> a, so f . g :: e -> a -> b

And finally:

doubleAndStringify :: Int -> String
doubleAndStringify d = show (d * 2)

valuesToInt doubleAndStringify // Int -> Int
(valuesToInt doubleAndStringify) 23 // 46 :: Int

Functors in Other Languages

We encounter functors all over the place:

Stream.of([1, 2, 3]).map(n -> n * 2) // a stream

// RxJs5
Observable<User> oUser = service.getUserById("1234");
Observable<EmailAddress> = oUser.map(x => x.emailAddress); // an observable

// ECMA-262 standard in the 5th edition
[1, 2, 3, 4].map(n => n * 3); // array

// underscore
let f = (n) => n * 4;
let g = (n) => n.toString();
let h = _.compose(g, f); // function composition

_applicative.md

What's an Applicative Functor?

From the docs, an applicative functor is a functor with application, providing operations to:

• embed pure expressions
• sequence computations and combine their results

Functors Aren't Sufficient

Given some types:

data EmailAddress = EmailAddress String deriving (Show, Eq)
data Password = Password String deriving (Show, Eq)

data Validated a = Fail String | Ok a deriving (Show, Eq)

data User = User EmailAddress Password

instance Functor Validated where
  fmap f (Ok x) = Ok (f x)
  fmap f (Fail s) = Fail s

...and some functions that validate user input:

toEmailAddress :: String -> Validated EmailAddress
toEmailAddress s = if (any (=='@') s) then Ok $ EmailAddress s
                   else Fail "bad email address: contained an ampersand"
                         
toPassword :: String -> Validated Password
toPassword s = if (length s > 5) then Ok $ Password s
               else Fail "bad password: too short"

we end up with the following four functions:

• a validator toEmailAddress, of type String -> Validated EmailAddress
• a validator toPassword, of type String -> Validated Password
• the User constructor, of type UserName -> EmailAddress -> Password -> User

Can we use fmap aka <$> here?

User <$> (toEmailAddress "whatever") :: Validated (Password -> User)

-- fmap :: Functor f => (a -> b) -> f a -> f b
-- User :: EmailAddress -> Password -> User
-- (a -> (b -> c)) -> f a -> f (b -> c)

So we have a Validated (Password -> User) and can create a Validated Password (via toPassword "whatever") - but we don't have any way to combine the two functors. Instead, we combine by hand:

createUser :: String -> String -> Validated User
createUser emailInput passwordInput = case (toEmailAddress emailInput) of
  (Fail m1, _) -> Fail m1
  (_, Ok email) -> case (toPassword passwordInput) of
    (Fail m2, _) -> Fail m2
    (_, Ok pw) -> Ok $ User email pw

The Applicative Type Class

As per the lecture, the Applicative type class gives us a way to apply functions which are themselves inside a Functor context to values in a Functor context.

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

Let's create an Applicative instance for the Validated type.

instance Applicative Validated where
  pure x = Ok x
  Ok f <*> Ok x = Ok (f x)
  Fail m <*> _ = Fail m
  _ <*> Fail m = Fail m

Now, we can rewrite our createUser function to use the new Applicative instance:

createUser :: String -> String -> Validated User
createUser emailInput passwordInput = User <$> toEmailAddress emailInput <*> toPassword password

Sequencing / Combining

If we want to change the way that errors are collected (currently, the first encountered error-message is the only one returned by our createUser function), we only need to modify our type class-instance:

instance Applicative Validated where
  pure x = Ok x
  Ok f <*> Ok x = Ok (f x)
  Fail m <*> Ok _ = Fail m
  Ok _ <*> Fail m = Fail m
  Fail m1 <*> Fail m2 = Fail (m1 ++ " + " ++ m2)

Applicative Functors in Other Languages

Lots of applicative functors in the real world, too:

// lodash 4.17.4

function User(name, age) {
  this.name = name;
  this.age = age;
}

// f a -> f b -> (a -> b -> c) -> f c
_.zipWith(["Bob", "Sally", "Yoshimi"], [10, 20, 30], function(name, age) {
  return new User(name, age);
});

// ECMAScript 2015 (6th Edition, ECMA-262)

const p1 = new Promise((resolve, reject) => { 
  setTimeout(resolve, 1000, 'Bob'); 
}); 

const p2 = new Promise((resolve, reject) => { 
  setTimeout(resolve, 2000, 35); 
});

// f a -> f b -> (a -> b -> c) -> f c
Promise.all([p1, p2]).then([name, age] => { 
  return new User(name, age);
});

// Rx

Observable<String> names = Observable.just("Sue", "Bob");
Observable<Integer> ages = Observable.just(25, 44);

// f a -> f b -> (a -> b -> c) -> f c
Observable<User> users = o1.zipWith(o2, (name, age) -> new User(name, age));