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
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. ???
instance Applicative Maybe where
pure = Just
Nothing <*> _ = Nothing
_ <*> Nothing = Nothing
Just f <*> Just x = Just (f x)
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
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
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
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)
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
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) }
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))
👍
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')
-- 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 intoParser (Char, Char)
(,) :: a -> b -> (a,b)
needs to be put into theParser
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!
Basically the same as abParser
Basically the same as intPair
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)
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 becauseposInt <|> (satisfy isUpper)
does not have the typef a -> f a -> f a
required by<|>