Functor and Applicative_Haskell Notes 7

I. Is Functor Like a Box?

Box Metaphor

Common Functor class instances seem can all be compared to boxes (or called containers), like Maybe/Either, List ([]):

> fmap (+1) (Just 3)
Just 4
> fmap (+1) (Right 3)
Right 4
> fmap (+1) [1, 2, 3]
[2,3,4]

Through fmap apply function to values inside container, get a similar container holding new values, even I/O Action can be understood this way:

> fmap (++"!") getLine
abc
"abc!"

I/O Action class container is special in that values inside are uncertain, depend on external input, may come from user typing, file reading, or even directly from system environment (like random number seed). But one thing is certain, I/O Action container holds a value (no matter where this value comes from), and fmap can apply function to this value, similarly get an I/O Action holding new value

Up to this point, box metaphor is still appropriate: containers in pure environment are wooden treasure chests, holding determined unchanging things inside, while containers in impure environment are man-eating treasure chests, don't know what's inside. As shown below (just past Children's Day, being playful):

[caption id="attachment_1722" align="alignnone" width="423"] functor and box[/caption]

Functions are Also Functor Class Instances?!

So, can all Functor class instances be understood this way?

instance Functor (Const m) -- Defined in 'Data.Functor.Const'
instance Functor (Either a) -- Defined in 'Data.Either'
instance Functor [] -- Defined in 'GHC.Base'
instance Functor Maybe -- Defined in 'GHC.Base'
instance Functor IO -- Defined in 'GHC.Base'
instance Functor ((->) r) -- Defined in 'GHC.Base'
instance Functor ((,) a) -- Defined in 'GHC.Base'

(Note: For simplicity, above only lists general Functor instances, removed 3 special Functor instances that also belong to Applicative)

Others are nothing special, ((->) r) looks a bit strange, looks like function definition (r map to something), look at definition:

instance Functor ((->) r) where
  fmap = (.)

((->) r) is indeed Functor class instance, implemented fmap is function composition (.):

(.) :: (b -> c) -> (a -> b) -> a -> c

Accepts a function mapping b to c and a function mapping a to b, connects latter's output to former's input, returns function mapping a to c. This is what we know as function composition, but what does it have to do with Functor?

First Functor's fmap type is:

fmap :: Functor f => (a -> b) -> f a -> f b

Since ((->) r) is also Functor instance, replace f with ((->) r):

fmap :: (a -> b) -> (->) r a -> (->) r b

Finally change -> to habitual infix form:

fmap :: (a -> b) -> (r -> a) -> (r -> b)

Isn't this function composition (.)?

(.) :: (b -> c) -> (a -> b) -> a -> c

So, functions are also Functor class instances

P.S. So, why does ((->) r) look so strange? Because Functor class requires:

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

f must be a type accepting one concrete type parameter (* -> *), while -> is:

(->) :: * -> * -> *

Has one extra parameter, so fill one first, get ugly (->) r (r is just a formal parameter name, can be called a or b)

More Appropriate Metaphor

Functions, indeed hard to think of as boxes. If imagination is really rich, can think of as biochemical boxes (Mothra), or cauldrons (a new card from Witchwood), boxes that can transform contents, hmm, test tubes

fmap at function level is function composition, against function mapping a to b, do a mapping of mapping b to c, get a new function mapping a to c:

instance Functor ((->) r) where
  fmap = (.)

(.) :: (b -> c) -> (a -> b) -> a -> c

Compare with previous box metaphor:

Through fmap apply function to values inside container, get a similar container holding new values

Substitute our invented biochemical boxes, get: through fmap apply (biochemical) boxes to (biochemical) boxes, get a new (biochemical) box

How to understand these 3 "(biochemical) boxes"?

Think of map a to b and map b to c as two test tubes, and if test tubes can connect, barely makes sense:

-- Test tube ab can turn water red
a -> b
-- Test tube bc can turn red water blue
b -> c
-- Mapping test tube bc onto ab is poking a hole in bottom of ab, fitting into test tube bc
(b -> c) . (a -> b)
-- Get a (longer) new test tube ac, function is to turn water blue
a -> c

Why compare to test tubes (or biochemical boxes)? Because refers to a transformation, want to express change. While our understood boxes lack this meaning of having transformation effect, therefore this metaphor is not appropriate

So, for Functor in function context

Box metaphor is not so appropriate, functors are actually more like computation. function being map over to a computation produces a computation mapped through that function

Above description is quite apt, computation is data transformation, and transformation can do mapping, way to do mapping is composition

A more correct description is functors are a computational context. This context might be that this computation might have a value, or might fail (like Maybe and Either a), or it might have multiple values (like lists), etc.

So, don't call it boxes, call it computational context, fmap is equivalent to adding a layer of transformation to this computational context (do mapping)

Lifting

Look at fmap's type definition again:

fmap :: Functor f => (a -> b) -> f a -> f b

Input a function mapping a to b and a Functor instance a, return another Functor instance b, nothing special

Look at it another way:

fmap :: Functor f => (a -> b) -> (f a -> f b)

Input a function mapping a to b, return another function, this function's effect is also mapping a to b, but within Functor's context (parameters and return values are all wrapped in Functor), seems to have some meaning

Converting a function to a corresponding function in another environment is called lifting:

Lifting is a concept which allows you to transform a function into a corresponding function within another (usually more general) setting.

Look at this example:

> replicate 3 'a'
"aaa"
> :t replicate
replicate :: Int -> a -> [a]
> :t liftA2 replicate
liftA2 replicate :: (Applicative f) => f Int -> f a -> f [a]
> (liftA2 replicate) [1,2,3] ['a','b','c']
["a","b","c","aa","bb","cc","aaa","bbb","ccc"]
> :t liftA2
liftA2 :: (Applicative f) => (a -> b -> c) -> (f a -> f b -> f c)

Where liftA2 does is lifting, according to a normal function (replicate) create a similar new function, new one that can be applied to another environment (Applicative context):

--  Normal function
Int -> a -> [a]
--  Lift it
f Int -> f a -> f [a]

So, lift is convenient for letting normal functions work normally in f's context

P.S. Similar lift functions total 3:

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

More parameters can be defined in seconds through <$> and <*>, see (->) r part in Applicative instances section below

II. Functor laws

Previously mentioned:

When implementing Functor need to follow some rules, like don't want List element order to change, want binary search tree to still retain its structural properties, etc.

(From [Deep dive into typeclass_Haskell Notes 4](/articles/深入 typeclass-haskell 笔记 4/))

So functor laws' function is to constrain fmap, let mapping results maintain some properties:

If functor laws are followed, we know doing fmap on it won't do extra things, just mapping with a function

Total 2 rules:

fmap id = id
fmap (f . g) = fmap f . fmap g

P.S. Second rule can also be written as fmap (f . g) F = fmap f (fmap g F), removing composition easier to understand

First rule, if we do map id on functor, then得到的 new functor should be exactly the same as original

Second rule, composing two functions together and mapping result over a functor should be exactly the same as first mapping first function over a functor, then mapping second function over the functor obtained from first step

(Built-in) Functor class instances all satisfy these two rules, for example:

> fmap id (Just 3)
Just 3
> fmap id Nothing
Nothing
> fmap ((+1) . (*2)) (Just 3)
Just 7
> fmap (+1) . fmap (*2) $ Just 3
Just 7

But manually implemented Functor instances may not, because these two rules are only moral constraints, no strong checks, so when implementing custom Functor instances should consciously comply

III. Applicative functors

Looking at name called enhanced version of Functor, so where is it stronger?

We know Functor circles a class of things that can be map over, can use fmap against Functor instances, apply normal functions to Functor's computational context

Seems powerful enough, but some special scenarios, for example:

> :t fmap (+) (Just 3)
fmap (+) (Just 3) :: Num a => Maybe (a -> a)

What is this thing? Maybe holds a function (i.e., Just (+3)), so how to take this function out to use?

For example if want to apply to Just 2, we do this:

> let (Just f) = (Just (+3)) in fmap f (Just 2)
Just 5

First pattern match extract (+3), then do (+3) mapping on Just 2, because we cannot purely use fmap to apply a function wrapped in a Functor to another value wrapped in a Functor

So is there a general pattern effective for any Functor that can help us complete this thing (apply a function inside a Functor to a value inside another Functor)?

Yes. This thing is Applicative:

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

(From Applicative)

Requires must be Functor instance first, so Applicative is a special kind of Functor, so also called Applicative functors

Defines two interfaces pure and <*>

pure puts a normal value into a default context, a minimal context but still containing this value

How to understand? Look at example:

> pure 1 :: [Int]
[1]
> pure 1 :: Maybe Int
Just 1
> pure 1 :: IO Int
1

For List而言，minimal context is [] (empty List), so putting 1 in gets [1]. For Maybe, Nothing has no value-storing ability, context can only be Just, so is Just 1. For I/O Action, of course is return 1 (put value into I/O Action through return)

<*>'s function is:

It applies the wrapped function to the wrapped value

This is exactly what we want, apply a function inside a Functor to a value inside another Functor

So, Applicative's enhancement to Functor is reflected in <*> function, enhancement way is to let these Functor instances all implement a <*>, support applying a function inside a Functor to a value inside another Functor

Brings 2 benefits, first is more friendly to multi-parameter functions:

If just normal functor, we can only map a (single-parameter) function over this functor. But with applicative functor, we can apply a (multi-parameter) function to multiple functors

Second is allows Functors to combine (unlike fmap calculate once get a Functor then can only end, through <*> can continue computing):

applicative functor is not just interesting but practical, it allows us to combine different kinds of computations, like I/O computations, non-deterministic computations, computations that might fail, etc. And using <$> and <*> we can apply normal functions to operate on any number of applicative functors.

For example:

> (+) <$> (Just 1) <*> (Just 2)
Just 3
> (\a b c -> a + b + c) <$> (Just 1) <*> (Just 2) <*> (Just 3)
Just 6
> (+3) <$> ((+) <$> (Just 1) <*> (Just 2))
Just 6

IV. Applicative instances

Applicative class has many instances:

instance Monoid m => Applicative (Const m)
  -- Defined in 'Data.Functor.Const'
instance Applicative (Either e) -- Defined in 'Data.Either'
instance Applicative ZipList -- Defined in 'Control.Applicative'
instance Monad m => Applicative (WrappedMonad m)
  -- Defined in 'Control.Applicative'
instance Control.Arrow.Arrow a => Applicative (WrappedArrow a b)
  -- Defined in 'Control.Applicative'
instance Applicative [] -- Defined in 'GHC.Base'
instance Applicative Maybe -- Defined in 'GHC.Base'
instance Applicative IO -- Defined in 'GHC.Base'
instance Applicative ((->) a) -- Defined in 'GHC.Base'
instance Monoid a => Applicative ((,) a) -- Defined in 'GHC.Base'

Maybe

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

For Maybe type, minimal context that can let values participate in computation is Just something, can't extract function from Nothing, so result must be Nothing, if left side is not Nothing, pattern match extract function f from it, and through fmap apply to right side's Maybe instance (something)

List

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

pure f is [f], while [f] <*> xs applies each function on left to each value on right

P.S. Easy to discover pure f <*> xs is actually equivalent to fmap f xs, this is also one of Applicative laws

IO

instance Applicative IO where
  pure = return
  a <*> b = do
    f <- a
    x <- b
    return (f x)

pure's corresponding implementation is return, wrap a value into I/O Action, let it participate in IO computation, <*>'s job is to extract function and value from left and right I/O Actions respectively, after doing computation wrap result with return

(->) r

instance Applicative ((->) r) where
  pure x = (\_ -> x)
  f <*> g = \x -> f x (g x)

This looks a bit strange, pure generates a function returning constant, <*> combines functions from left and right sides

For example:

(+) <$> (+3) <*> (*100)

Where <$> is infix version of fmap, as follows:

infixl 4 <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<$>) = fmap

<*> and <$> are both infixl 4 (infix left associative, priority is 4), so expansion process is like this:

(+) <$> (+3) <*> (*100)
=(fmap (+) (+3)) <*> (*100)
=((.) (+) (+3)) <*> (*100)
=((+) . (+3)) <*> (*100)
=\x -> ((+) . (+3)) x ((*100) x)
=\x -> (+) ((+3) x) ((*100) x)

That is:

f1 <$> f2 <*> f3
=\x -> f1 (f2 x) (f3 x)

Feeding two applicative functors to <*> can produce a new applicative functor, so if we throw two functions at it, we can get a new function

So actual effect of f1 <$> f2 <*> f3 is: create a function that takes results of f2 and f3 as parameters to call f1. So there is:

f1 <$> f2 <*> f3 <*> ... <*> fn
=\x -> f1 (f2 x) (f3 x) ... (fn x)

P.S. This fixed pattern of f1 <$> f2 <*> f3 has a utility function, called liftA2:

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

liftA2 accepts a normal binary function, and upgrades it to a function that can operate on two functors

This is so-called lifting (upgrade?)

ZipList

Compare with List:

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

ZipList's implementation is as follows:

instance Applicative ZipList where
  pure x = ZipList (repeat x)
  ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)

P.S. ZipList is located in Control.Applicative module, reason ZipList exists is because cannot give List another different Applicative implementation

pure actually generates an infinitely long ZipList, this is because zipWith result is based on shorter of two Lists, so, to guarantee x can normally participate in computation (satisfy arbitrary length List on other side), so for ZipList而言，ZipList (repeat x) is that minimal context

<*> is to extract function List from left side, extract data List from right side, then pair elements of two Lists one by one to do mapping (zipWith)

Let left side function List have only same function, equivalent to using this function to map over right side List:

> getZipList $ pure (+1) <*> (ZipList [1, 2, 3])
[2,3,4]

P.S. Where getZipList :: ZipList a -> [a] is a getter (see [Types_Haskell Notes 3 | Record](/articles/类型-haskell 笔记 3/#articleHeader8) for details), used to extract List inside

Change it up:

> getZipList $ (+) <$> ZipList [1, 2, 3] <*> (ZipList [1, 2, 3])
[2,4,6]
> getZipList $ max <$> ZipList [1, 3, 4, 5] <*> ZipList [2, 0]
[2,3]

V. Applicative laws

Similarly, Applicative also needs to follow some rules:

pure f <*> x = fmap f x
pure id <*> v = v
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
pure f <*> pure x = pure (f x)
u <*> pure y = pure ($ y) <*> u

Through pure let normal function f can participate in Functor computation, so there is:

pure f <*> x = fmap f x
pure id <*> v = v
pure f <*> pure x = pure (f x)

Through <*> let function in left Functor can apply to value in right Functor, so:

-- $ fixes parameter position
u <*> pure y = pure ($ y) <*> u
-- (.) changes associativity
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

Built-in Applicative instances all comply with these rules, but similarly only moral constraints, when manually implementing Applicative instances need to consciously comply

Applicative style

Through <$> and <*> can achieve very elegant applicative calling style. For example:

> (++) <$> Just "johntra" <*> Just "volta"
Just "johntravolta"

Compare with function call:

> (++) "johntra" "volta"
"johntravolta"

Even more obvious in I/O scenario:

myAction = do
  a <- getLine
  b <- getLine
  return $ a ++ b

Corresponding applicative style:

myAction = (++) <$> getLine <*> getLine

Quite elegant, makes computation at Functor level almost no difference in form from normal computation (eliminates difference of context where computation is located from form perspective)