Applicative Functor (part 1) notes

Applicative Functor (part 1) notes.md

Applicative functors

Why is Applicative Functor needed?

To understand the need for applicative, try to write an implementation of the following:

fmap2 :: Functor f => (a -> b -> c) -> (f a -> f b -> f c)

TL;DR you can't.

Quick explanation:

Given:

h :: a -> b -> c
fa :: f a
fb :: f b

Map h over fa: fmap h fa :: f (b -> c)

Observe that you cannot, using Functor alone, combine f (b -> c) and f b to get f c. You need a function with the type f (b -> c) -> f b -> f c. Lo and behold, that's what <*> is in the Applicative typeclass:

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

Pure?

Perhaps interestingly, in the same way <*> is used to implement fmap2, pure is used to implement fmap0. Here's what they look like alongside fmap:

pure (aka fmap0) ::  a -> f a
fmap             :: (a -> b)      -> (f a -> f b)
fmap2            :: (a -> b -> c) -> (f a -> f b -> f c)

Q. Why is this worth pointing out?

A. ???

Maybe Applicative

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

My Attempt To Understand The Applicative Laws

pure id <*> v = v                               -- Identity
pure f <*> pure x = pure (f x)                  -- Homomorphism
u <*> pure y = pure ($ y) <*> u                 -- Interchange
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)    -- Composition

Where:

y     :: a
w     :: f a
u     :: f (a -> b)
v     :: f (a -> b) -- also written as f (b -> c), but they really mean the same thing

id    :: a -> a
pure  :: a -> f a
($)   :: (a -> b) -> a -> b
(.)   :: (b -> c) -> (a -> b) -> a -> c
(<*>) :: f (a -> b) -> f a -> f b

Identity: pure id <*> x = x

x :: f a

  pure id <*> x
= pure id <*> f a
= pure (a -> a) <*> f a
= f (a -> a) <*> f a
= f a
---
  f a

This is like any other identity law, and can be demonstrated in ghci using Maybe (which is an Applicative Functor):

> let x = Maybe 10
> (pure id <*> x) == x
True

Homomorphism: pure h <*> pure x = pure (h x)

This is the law that is noted in the lecture as being the only "interesting" law for Applicative.

x :: a
h :: a -> b

  pure h <*> pure x
= pure h <*> pure a
= pure (a -> b) <*> pure a
= pure (a -> b) <*> f a
= f (a -> b) <*> f a
= f b
---
  pure (h x)
= pure (h a)
= pure ((a -> b) a)
= pure b
= f b

Remember that a homomorphism is basically just a map. This law says applying the map with function application before involving functor has the same result as applying the map with functor applicatin after involving functor. This can be demonstrated in ghci using Maybe:

> let x = 10
> let h = (+13)
> (pure h <*> pure x :: Maybe Integer) == (pure (h x) :: Maybe Integer)
True

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

y :: a
u :: f (a -> b)

  u <*> pure y
= u <*> pure a
= u <*> f a
= f (a -> b) <*> f a
= f b
---
  pure ($ y) <*> u
= pure ($ y) <*> f (a -> b)
= pure ($ a) <*> f (a -> b)
= pure (`((a -> b) -> a -> b)` a) <*> f (a -> b)
      -- Note that I use backticks (`...` ) here to indicate that
      -- the function is to be applied as if it were an infix operator,
      -- the result of which can be seen in the next step
= f (`((a -> b) -> a -> b)` a) <*> f (a -> b)
= f ((a -> b) -> b) <*> f (a -> b)
= f b

This law appears to say that you can exchange the order of the arguments during functor application and get the same result. This can be demonstrated in ghci using Maybe:

> let y = 15
> let u = pure (+17)
(u <*> pure y :: Maybe Integer) == (pure ($ y) <*> u :: Maybe Integer)

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

u :: f (b -> c)
v :: f (a -> b)
w :: f a

  pure (.) <*> u <*> v <*> w
= pure (.) <*> u <*> v <*> f a
= pure (.) <*> u <*> f (a -> b) <*> f a
= pure (.) <*> f (b -> c) <*> f (a -> b) <*> f a
= pure ((b -> c) -> (a -> b) -> a -> c) <*> f (b -> c) <*> f (a -> b) <*> f a
= f ((b -> c) -> (a -> b) -> a -> c) <*> f (b -> c) <*> f (a -> b) <*> f a
= f ((a -> b) -> a -> c) <*> f (a -> b) <*> f a
= f (a -> c) <*> f a
= f c
---
  u <*> (v <*> w)
= u <*> (v <*> f a)
= u <*> (f (a -> b) <*> f a)
= u <*> f b
= f (b -> c) <*> f b
= f c

Like the name implies, this law says that functor application and function composition within functor produce the same result. This can be demonstrated in ghci using Maybe:

> let u = pure (+8)
> let v = pure (+12)
> let w = pure 5
> (pure (.) <*> u <*> v <*> w :: Maybe Integer) == (u <*> (v <*> w) :: Maybe Integer)
True

Homework

Parser: takes unstructured data as input and produces structured data as output.

In the assignment, a parser of type a takes a String and returns an a along with the rest of the String. If the a cannot be created, then Nothing is returned.

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

Functor Parser

Q. What exactly does it mean to fmap over a Parser?

A. Given a function a -> b and a Parser of some type a, return a Parser of some type b:

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

--- Exercise 1

Implement fmap :: (a -> b) -> Parser a -> Parser b using:

Relevant types --

• p :: Parser a
• h :: (a -> b)
• runParser :: Parser a -> String -> Maybe (a, String)
• fmap :: (a -> b) -> f a -> f b
• first :: (a -> b) -> (a, c) -> (b, c)
• fmap h ((->) e) :: (a -> b) -> (e -> a) -> (e -> b)

Which can be combined --

• runParser p :: String -> Maybe (a, String)
• first h :: (a, c) -> (b, c)
• fmap (first h) :: Maybe (a, c) -> Maybe (b, c)
• fmap (fmap (first h)) (runParser p) :: String -> Maybe (b, String)
• Parser (fmap (fmap (first h)) (runParser p)) :: Parser (String -> (b, String)) Aha!

And so --

instance Functor Parser where
  fmap = Parser (fmap (fmap (first h)) (runParser p))

👍

Applicative Functor Parser

Q. What exactly does it mean to ap over a Parser?

A.

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

-- Exercise 2

---- pure

Parser is constructed with a String -> Maybe (a, String). The implementation, given some value of type a is Parser (\s -> Just (a,s)).

class Functor Parser => Applicative Parser where
  pure a = Parser (\s -> Just (a,s))
  ...

---- <*>

Basically, just run the parser, if there is a result, run the parser over that result, otherwise return Nothing.

class Functor Parser => Applicative Parser where
  p <*> g = Parser (\s ->
      case runParser p s of
      Nothing       -> Nothing
      Just (f',s')  -> runParser (fmap f' g) s')

abParser

-- Exercise 3

---- abParser :: Parser (Char, Char)

The goal is to provide an implementation of abParser using <*>. Here's an unacceptable, but correct implementation:

abParser_ :: Parser ()
abParser_ = Parser (\s ->
  case s of
    ('a':'b':s') -> Just (('a','b'), s')
    _ -> Nothing)

But I want to do this using <*>.

Relevant types --

• (,) :: a -> b -> (a,b)
• (<$>) :: a -> f a
• (<*>) :: f (a -> b) -> f a -> f b
• char :: Char -> Parser Char

Which can be combined --

• The functor context here is Parser
• The goal is to take two Parser Char and combine them into Parser (Char, Char)
• (,) :: a -> b -> (a,b) needs to be put into the Parser context, then applied to two other parsers
• (<$> (,)), in this context, has type :: Parser (a -> b -> (a,b))
• Use <$> :: f (a -> b) -> f a -> f b:
  • (<$> (,)) :: Parser (a -> b -> (a,b))
  • (,) <$> char 'a' :: Parser (b -> (a,b))
  • (,) <$> char 'a' <*> char 'b' :: Parser (a,b) Aha!

abParser

Basically the same as abParser

intPair

Basically the same as intPair

Alternative Parser

class Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a

-- empty

Always results in Nothing:

instance Alternative Parser where
  empty = Parser (const Nothing)
  ...

-- <|>

Simply run the first parser, if the result is Nothing, then return the result of the second parser:

instance Alternative Parser where
  ...
  p <|> p' = Parser (\s ->
    case runParser p s of
      Nothing -> runParser p s
      r       -> r)

Can I simplify this?

Relevant types --

• <|> :: f a -> f a -> f a
• <$> :: (a -> b) -> f a -> f b
• <*> :: f (a -> b) -> f a -> f b
• pure :: a -> f a
• Parser :: (String -> Maybe (a, String)) -> Parser a

Which can be combined --

p                        :: String -> Maybe (a, String)
g                        :: String -> Maybe (a, String)
(<|>)                    :: Maybe a -> Maybe a -> Maybe a
pure (<|>)               :: Parser (Maybe a -> Maybe a -> Maybe a)
pure (<|>) <*> p         :: Parser (Maybe a -> Maybe a)
pure (<|>) <*> p <*> g   :: Parser (Maybe a)   -- Aha!

Parser p <|> Parser g = Parser (pure (<|>) <*> p <*> g)

intOrUppercase

Relevant types --

isUpper   :: Char -> Bool
const     :: a -> b -> b
pure      :: a -> Parser a
<|>       :: Parser a -> Parser a -> Parser a
satisfy   :: (Char -> Bool) -> Parser Char
posInt    :: Parser Integer
char      :: Char -> Parser Char
<*>       :: Parser (a -> b) -> Parser a -> Parser b

Which can be combined --

unit' = const ()                     :: a -> ()
unit' <$> posInt                     :: Parser ()
satisfy isUpper                      :: Parser Char
unit' <$> (satisfy isUpper)          :: Parser ()

(unit' <$> posInt) <|> (unit' <$> (satisfy isUpper)) :: Parser () -- Aha!

• The use of posInt, satisfy isUpper and <|> seem obvious.
• const () <$> is used because posInt <|> (satisfy isUpper) does not have the type f a -> f a -> f a required by <|>