What is a number? You normally don't ask that, nor do you answer it directly. Perhaps you answer indirectly: examples, how to use numbers, how to work with numbers, some properties (axioms and theorems) like how addition is commutative. And lastly, you learned numbers by practice.
Likewise with vector spaces. Remember those? Your best bet at teaching or learning them is again through examples, applications, properties, and ultimately practice.
The same approach is best for functor and applicative. Don't seek a direct answer to “what is an applicative?”. Do look for and work out more examples, applications, properties. If you can write correct code, fix incorrect code, and predict the outcome of other people's code, you already understand more than you think, even if you can't write a sounds-good essay.
Practice. 40 hours a day.
This is the standard library map function (e.g., map f [x,
y, z] = [f x, f y, f z]) but I give it a different name:
fmap_List :: (a -> b) -> [] a -> [] b -- "[] a" means "[a]" in types. fmap_List f [] = [] fmap_List f (x:xs) = f x : fmap_List f xsin FunctorsApplicatives.hs
Definition of the Maybe type from the standard library:
data Maybe a = Nothing | Just a
Two perspectives:
There is a function for Maybe analogous to fmap_List:
fmap_Maybe :: (a -> b) -> Maybe a -> Maybe b fmap_Maybe f Nothing = Nothing fmap_Maybe f (Just a) = Just (f a)in FunctorsApplicatives.hs
Definition of the Either type from the standard library:
data Either e a = Left e | Right a
It's like Maybe, but the “no answer” case carries extra data,
perhaps some kind of reason for why “no answer”.
And you guessed it, there is an analogous function for Either:
fmap_Either :: (a -> b) -> (Either e) a -> (Either e) b fmap_Either f (Left e) = Left e fmap_Either f (Right a) = Right (f a)in FunctorsApplicatives.hs
Also arrays, dictionaries, tree structures,… most polymorphic data structures you can think of, and then some.
Common theme: (a -> b) -> (F a -> F b),
where F is a parametrized type. There is a class for that!
class Functor f where
fmap :: (a -> b) -> (f a -> f b)
A data structure example:
data BinTree a = BTNil | BTNode a (BinTree a) (BinTree a) deriving Show
instance Functor BinTree where
-- fmap :: (a -> b) -> BinTree a -> BinTree b
fmap f BTNil = BTNil
fmap f (BTNode a lt rt) = BTNode (f a) (fmap f lt) (fmap f rt)
in FunctorsApplicatives.hs
fmap should satisfy these two axioms/laws:
-- 1. Functor identity fmap (\x -> x) xs = xs -- i.e., fmap (\x -> x) = \xs -> xs -- i.e., fmap id = id -- and to elaborate the types, since there are two "id"s: fmap (id :: a -> a) = (id :: f a -> f a) -- 2. fmap fusion, fmap is a homomorphism fmap g (fmap f xs) = fmap (\x -> g (f x)) xs -- i.e., fmap g . fmap f = fmap (g . f)
Discussion:
If you notice that, for data structures, fmap seems to always
clone the shape and apply f elementwise to the elements, you're right. The
axioms are saying this very abstractly and indirectly. Example: If you tried to
be naughty and write fmap for BinTree to perform a
left-rotation at root, you would break both axioms. (Exercise: How?)
Functor on its own says very little, but it is an important starting point for defining very interesting and useful things. In programming, it is the step before Applicative below (and Monad later); there is also an advanced use (if you want this rabbit hole: “lens”). In category theory (another rabbit hole), most interesting definitions and theorems involve functors.
fmap can apply a unary function elementwise to one list (or one
Maybe, or…).
What if you want to apply a 2-ary function to all pairs of elements of two lists, like applying the 2-ary function to the cartesian product? I mean like this:
liftA2_List (-) [10,20,30] [1,2,3] = [10-1, 10-2, 10-3, 20-1, 20-2, 20-3, 30-1, 30-2, 30-3] = [9,8,7,19,18,17,29,28,27]
We can code up that much, and analogously for Maybe and other types:
liftA2_List :: (a -> b -> c) -> [a] -> [b] -> [c] liftA2_List f [] _ = [] liftA2_List f (a:as) bs = map (f a) bs ++ liftA2_List f as bs liftA2_Maybe :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c liftA2_Maybe f Nothing _ = Nothing liftA2_Maybe f (Just a) Nothing = Nothing liftA2_Maybe f (Just a) (Just b) = Just (f a b) -- The last two lines could be merged into: -- liftA2_Maybe f (Just a) mb = fmap (f a) mb liftA2_Either :: (a -> b -> c) -> Either e a -> Either e b -> Either e c liftA2_Either f (Left e) _ = Left e liftA2_Either f (Right a) (Left e) = Left e liftA2_Either f (Right a) (Right b) = Right (f a b) -- The last two lines could be merged into: -- liftA2_Either f (Right a) eb = fmap (f a) ebin FunctorsApplicatives.hs
The harder question is: What if you have a 3-ary function and three lists? Four?... I.e., if you want these:
liftA3_List :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d] liftA4_List :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e] etc.
do they have to be coded up from scratch?
It turns out: No need, they can be derived from liftA2_List:
liftA3_List :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
liftA3_List f as bs cs =
let gs = liftA2_List f as bs
-- Think f :: a -> b -> (c -> d)
-- So gs :: [c -> d]
ds = liftA2_List (\g c -> g c) gs cs -- [d]
in ds
liftA4_List :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]
liftA4_List f as bs cs ds =
let gs = liftA2_List f as bs -- [c -> d -> e]
hs = liftA2_List (\g c -> g c) gs cs -- [d -> e]
es = liftA2_List (\h d -> h d) hs ds -- [e]
in es
in FunctorsApplicatives.hs
Example showing liftA3_List f [i,j] [m,n] [x,y]:
gs = liftA2 f as bs = liftA2 f [i,j] [m,n] = [f i m, f i n, f j m, f j n] ds = liftA2 (\g c -> g c) gs cs = liftA2 (\g c -> g c) [f i m, f i n, f j m, f j n] [x, y] = [f i m x, f i m y, f i n x, f i n y, f j m x, f j m y, f j n x, f j n y]
Analogous stories for Maybe and Either.
(Unfortunately not BinTree.)
There is a class for this too! It's called Applicative because it generalizes function application (explained below):
class Functor f => Applicative f where
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
(<*>) :: f (a -> b) -> f a -> f b
-- You can pronouce <*> as "ap". Explanation below.
-- Left-associative: foo <*> bar <*> caz = (foo <*> bar) <*> caz
pure :: a -> f a
-- And default implementations because <*> and liftA2 are definable by each other.
-- So an instance can omit one of them.
fs <*> as = liftA2 (\f a -> f a) fs as
liftA2 f as bs = fmap f as <*> bs
-- And a couple of other methods with easy default implementations.
Explanation of <*>: We saw “liftA2 (\g c -> g
c)” several times; it shows up often enough to deserve a name. It brings
function application (\g c -> g c) to the f type, and
we call it “ap”. Historically, it was thought up first, liftA2 a
tiny little bit later.
Example showing why fmap f as <*> bs does the same thing
as liftA2 f as bs:
fmap f [i,j] <*> [m,n] = [f i, f j] <*> [m,n] = [f i m, f i n, f j m, f j n] = liftA2 f [i,j] [m,n]
Here is how to use <*> and fmap to also
obtain liftA3, liftA4:
-- Actually already in Control.Applicative liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d liftA3 f as bs cs = (fmap f as <*> bs) <*> cs liftA4 :: Applicative f => (a -> b -> c -> d -> e) -> f a -> f b -> f c -> f d -> f e liftA4 f as bs cs ds = ((fmap f as <*> bs) <*> cs) <*> dsin FunctorsApplicatives.hs
Explanation of pure: for [], Maybe,
and Either e:
-- [] version pure a = [a] -- Maybe version pure a = Just a -- Either e version pure a = Right a
pure plays two roles:
The degenerate case when you have a 0-ary function and 0 lists, kind of.
2-ary, liftA2 :: (t1 -> t2 -> a) -> F t1 -> F t2 -> F a 1-ary, fmap :: (t1 -> a) > F t1 -> F a 0-ary, pure :: a -> F a
fmap can be defined from pure and one
of <*>, liftA2:
fmap f xs = pure f <*> xs = liftA2 (\f x -> f x) (pure f) xs
This is the mathematical reason for putting Applicative as a subclass of Functor.
The Applicative methods should satisfy the following axioms. They are stated with
<*> rather than liftA2, so this is one reason to
still learn <*>. The associativity axiom is pretty abstract,
but I will show some corollaries below that hopefully helps.
-- 0. Applicative subsumes Functor
fmap f xs = pure f <*> xs
-- 1. Applicative left-identity
pure id <*> xs = xs
-- Compare with fmap identity! fmap id xs = xs
-- 2. Applicative associativity, composition
gs <*> (fs <*> xs) = ((pure (.) <*> gs) <*> fs) <*> xs
= (liftA2 (.) gs fs) <*> xs
-- Analogy: g (f x) = (g . f) x
-- It may help to elaborate the types. Assume:
-- xs :: f a
-- fs :: f (a -> b)
-- gs :: f (b -> c)
-- (.) :: (b -> c) -> (a -> b) -> (a -> c)
-- Try to determine the types of the subexpressions.
-- 3. pure fusion, pure is a homomorphism
pure f <*> pure x = pure (f x)
fmap f (pure x) = pure (f x)
-- 4. pure interchange, almost right-identity
fs <*> pure x = pure (\f -> f x) <*> fs
= fmap (\f -> f x) fs
A corollary is that the Applicative axioms imply the Functor axioms
given fmap f xs = pure f <*> xs. Functor identity is
immediate from Applicative left-identity. To deduce fmap fusion:
fmap g (fmap f xs) in Applicative terms = pure g <*> (pure f <*> xs) associativity = ((pure (.) <*> pure g) <*> pure f) <*> xs pure fusion = (pure ((.) g) <*> pure f) <*> xs pure fusion = pure ((.) g f) <*> xs infix notation = pure (g . f) <*> xs in Functor terms = fmap (g . f) xs
Another corollary is that
liftA3 (\x y z -> x + (y + z)) xs ys zs
can be done by the following two equivalent ways:
(fmap (\x y z -> x + (y + z)) xs <*> ys) <*> zs = fmap (+) xs <*> (fmap (+) ys <*> zs)
The first way you already know, and it associates to the left. The second way associates to the right. Intuitively, you have some kind of associativity law. In the case of lists, it says that the two cartesian products (R×S)×T and R×(S×T) are equivalent. The proof (6 steps of algebra grinding and 4 steps of lambda calculus perseverence) is omitted.
Associative laws justify re-grouping. This is important for refactoring and implementing long chains by recursion.
Example: You are tasked to implement
adds :: Applicative f => [f Integer] -> f Integerthat behaves as e.g.
adds (xs : ys : []) = liftA2 (\x y -> x + y) xs ys
= liftA3 (\x y z -> x + (y + z)) xs ys (pure 0)
adds (ws : xs : ys : []) = liftA4 (\w x y z -> w + (x + (y + z))) ws xs ys (pure 0)
It seems unclear how to do it generally by recursion. But associativity says:
adds (xs : ys : []) = fmap (+) xs <*> (fmap (+) ys <*> pure 0) adds (ws : xs : ys : []) = fmap (+) ws <*> (fmap (+) xs <*> (fmap (+) ys <*> pure 0))
Now it is almost telling you how to solve it!