Functional Patterns: Zips and the Applicative

This is part 5 of a series of articles entitled Functional Patterns.

Make sure to check out the rest of the articles!

1. The Monoid
2. Compositions and Implicitness
3. Interfaces and Functors
4. Recursion and Reduces

Functor Recap

Learning about Functors have taught us the very important function that is fmap, or mapping a function on a Functor interface (most commonly on the array).

Remember, the Functor interface differs from the actual term functor. Members of the interface Functor,
to put simply, can be mapped over by endofunctors (which are a type of a function that maps a category to
itself).

# python
map( lambda a: a**2, [1, 2, 3] )  # [1, 4, 9]

Mapping a function on an array is a pretty common operation, a transformation on your data, if you may. But what if we wanted to apply a different function to each element? In terms of using map (or fmap), we are out of luck, as the functor supported by map are applied to all of the elements.

Zips

Say we have an array of int, our points in a game show. We'll get this in array for every round of the game.

# points per round
 [4, 3, 8, 1]
# r1 r2 r3 r4

We'd like to get the total of our score. However, we are told that points are worth more in the later rounds! That is, every point is worth the round it was gained in.

[
    4 * 1,
    3 * 2,
    8 * 3,
    1 * 4
]

Let's try to get these values programatically. Let's first take an imperative approach, by using the index of our current value + 1 to multiply at our current number. We'll do this in Go, for a clearer demonstration:

rounds := []int{ ... }
result := 0

for (i := 0; i < len(rounds); i++) {
   result += rounds[i] * (i+1)
}

return result

then in Python:

rounds = [ ... ]
result = 0

for round, score in enumerate(rounds):
    result += score * (round + 1)

return result

We achieve pretty similar code, except for how we're now using a function named enumerate. Now what exactly does enumerate do?

enumerate(["a", "b", "c", "d"]) # [ (0, "a"), (1, "b"), (2, "c"), (3, "d") ]

Ah, the enumerate function "maps" some function to our original array, turning it into an array of pairs containing the index and the original value. But this can't be any ordinary functor, since there can't be any function that can achieve this changing value without side-effects!

Let's try to work backwards, and separate the pairs into their own arrays.

a = [ 0,   1,   2,   3 ]
b = ["a", "b", "c", "d"]

It shouldn't be that hard to get back to our paired array.

a = [ 0,   1,   2,   3 ]
b = ["a", "b", "c", "d"]
result = []

for i in range(len(b)):
    c.append( (a[i], b[i]) )

return c

We can simplify this further by realizing our a array is actually just range(len(b)).

a = range(len(b))
b = ["a", "b", "c", "d"]
result = []

for i in a:
    result.append( (i, b[i]) ):

return result

# also can be written as
# [ (i, b[i]) for i in a ]

Now we've implemented a function that takes two arrays a and b, and pairs them up into a resulting array! This is called the zip function. And the enumerate function is just a specialization of this, a zip with the first argument as the range(len(b)) of the second argument.

This is a simplified implementation for Python, as zip and enumerate actually return generators, and
mostly likely don't need to use range as a dependency.

b = ["a", "b", "c", "d"]
[*zip(range(len(b))], b) == [*enumerate(b)]  # [ (0, "a"), (1, "b"), (2, "c"), (3, "d") ]

Also, we've unlocked a whole new world for our map function, since now we can do differing partial applications for every element!

-- haskell
zip [3 .. 5] [9 .. 11] == [ (3, 9), (4, 10), (5, 11) ]
-- moreover, since functions are values...
zip [1 .. 3] [(*4), (+5), negate] == [ (1, (*4)), (2, (+5)), (3, negate)]

And since now we're in the array category once again, we can simply map or reduce over these pairs to perform our transformation!

points = [4, 3, 8, 1]

-- we pattern match on the tuple to multiply both elements
sum . map (\(a,b) -> a * b) . zip [1..] $ points

-- alternatively we can use the `uncurry` function, which does that
sum . map (uncurry (*)) . zip [1..] $ points

-- uncurry and mapping a zip is such a common pattern that it can be written as `zipWith`
sum . zipWith (*) [1..] $ points

-- point-free definition
totalScore = sum . zipWith (*) [1..]

Applicatives

A much more specific interface that is relevant to us is the Applicative typeclass.

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

What this means is that:

• in order to be Applicative, you first must be an instance of Functor.
• You have to define a function pure, which takes any type and then wraps it with your type constructor f (again, this is synonymous to a struct)
• You have to define a function <*>, which applies a wrapped function f (a -> b) to your wrapped value f a resulting in a wrapped result f b.

The following are additional axioms that need to be fulfilled ontop of being a valid member of the Functor typeclass. You don't have to fully understand these right now, but I figured I shouldn't omit them.

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

• The identity axiom states that applying a wrapped id (identity function) does nothing, working like the unwrapped id function.
• The homorphism axiom states that applying a wrapped function to a wrapped value is equal to applying the function to the value and then wrapping it.
• The interchange axiom states that applying u to a wrapped value is equal to applying a wrapped partial application of $ (thrush) of the original value to the function.
  • ($ a) f is the same as f $ a or f a.
• The composition axiom states that applying a wrapped (.) (composition function, b-combinator) is equal to composing the applied function to the following applications.

If we look at the signatures of the two main functions here fmap and <*>:

fmap  ::   (a -> b) -> f a -> f b
(<*>) :: f (a -> b) -> f a -> f b

We see that the only difference between these two is that Applicative has your functor wrapped in the same category (or data type) as your inputs!

The Maybe Monad

A ubiquitous Monad (which requires it be an Applicative) is the Maybe monad. We won't be talking about its Monad aspects here but what it does, to put simply, is act as context for functions with optional returns.

data Maybe m = Just m | Nothing

What this says is: Maybe is a data type (can be thought of as a struct) that holds type m and can either be a Just m or Nothing. An example of a function using this data type is:

findIndex :: (a -> Bool) -> [a] -> Maybe Int

findIndex even [1, 3, 4, 5] == Just 2
findIndex even [1, 3, 5] == Nothing

What findIndex does is find the first index wherein a predicate returns True. Now of course, this has a case wherein the predicate never returns True, and what would we return in that case? This is where the Maybe monad comes in, by wrapping our result in the Maybe type, we can return a Nothing in this case, and when we do find a True case, we just have to wrap our return with Just.

And if we're certain that we will always return a Just, we can just unwrap it using the fromJust function.

Since Maybe is under the Monad interface, and therefore an Applicative and Functor, we can do the things we were able to do on Applicative and Functor on it.

-- Being a functor:
fmap (* 2) (Just 4) == Just 8   -- we can map on it because its a functor, removing the need to unwrap
fmap (* 2) Nothing  == Nothing  -- which allows us to safely do operations on it.

But what if we needed to perform operations on multiple instances of a Maybe? We would have to unwrap them both, and then apply the function, right? However, this poses as risk— as unwrapping a Nothing will cause a runtime error, and writing all of that is just, horrible.

import Data.Maybe

Just (fromJust (Just 4)) + (fromJust (Just 5))  -- Just 9
Just (fromJust Nothing + (fromJust (Just 5))    -- ERROR!

Applicative allows us to compose functions without unwrapping our data types using the <*> function! Recall that all it does is apply a wrapped function, so we simply need to get to that point first. This is made more terse by the infix version of our lovely fmap function, written as <$>.

-- `pure` typed in the context of `Maybe Int` wraps our value in Just.
(pure 5) :: Maybe Int == Just 5

-- Applying a wrapped function
Just negate <*> Just 5 == Just (-5)
Just (+5)   <*> Just 2 == Just 7

-- Applying Nothing on either side resolves to Nothing
Nothing     <*> Just 5 == Nothing
Just (+5)  <*> Nothing == Nothing

fmap (+2) (Just 3) == Just 5
(+2) <$> Just 3    == Just 5        -- infix

(+) <$> Just 5 == Just (+5)         -- we get a wrapped *partially applied* function!

-- Therefore ..

(+) <$> Just 4 <*> Just 5 == Just 9   -- Composition!
(+) <$> Just 4 <*> Nothing == Nothing -- Composition!

The Maybe is analogous to Rust's Option type (although they do not have a way of simply composing these types), in that it can be used to avoid using sentinel or null values in your code altogether! This can even be further extended to handle errors in your code as a Nothing always propagates throughout the composition.

The ZipList Applicative

From reading the documentation, we actually find out that [] is also a data type of the Monad interface, again making it an Applicative and a Functor. We won't be demonstrating it's Functor properties as we've already covered that in a previous part of the series.

-- `pure` in the context of `[Int]` creates a singleton list
(pure 5) :: [Int] == [5]

-- Applying a list of functions to a singleton list returns a list of the applications!
[negate] <*> [5] == [-5]
[(*3), abs, (+2)] <*> [5] == [15, 5, 7]

-- Applying to our empty list always returns an empty list
[] <*> [3, 4] == []
[(*3), abs, (+2)] <*> [] == []

-- Applying a list of functions to a list of elements, performs a cartesian product
[(+2), (*3)] <*> [5, 2, 1] == [7, 15, 4, 6, 3, 3]

What's interesting with the list of functions applied to a list of values is that: it performs the function on all combinations of the functions and elements. Moreover, they are kept in a flattened list. This would be equivalent to:

result = []

for x in values:
    for f in functions:
        result.append(f(x))

# or
[ f(x) for x in values for f in functions ]

All within a single line.

We can actually implement the zip behavior of lists using an Applicative interface!

Let us define a ZipList data type.

-- we define our struct that holds an array of `a`
data ZipList a = ZipList { getZipList :: [a] }

-- we define its membership to the Functor typeclass
instance Functor Ziplist where
    -- we say that mapping on a ZipList is just mapping over its embedded array
    fmap f (Ziplist a) = Ziplist (map f a)

instance Applicative ZipList where
    -- we say that applying a list of wrapped functions is just zipping over wrapped values
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

However, we lack one definition here: pure. I've intentionally skipped this because this is a good demonstration to show where the axioms come into play.

Say we define the following:

pure x = ZipList [x]   -- mirroring the definition for `pure` of [], we put x in a singleton list

Recall that according to the identity axiom:

pure id <*> v == v

This definition falls apart when we substitute v as the infinite list [1..]

pure id <*> v == v

ZipList [id] <*> [1..] == ZipList [1..]
ZipList (zipWith ($) id [1..]) == ZipList [1..] -- zipWith truncates based on the shorter list
Ziplist [1] != ZipList [1..]                    -- false!

The problem with zip is that it truncates based on the shorter list, meaning for an application to be valid, the list fs must be infinite! So the definition of pure follows from that.

instance Applicative ZipList where
    -- we say that applying a list of wrapped functions is just zipping over wrapped values
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

    -- We say that the `pure` of some element x, is the infinite list of itself
    pure x = ZipList (repeat x)

And if you think about it— applying an infinite list of id to a finite list of x, will always return you the original list! Cool!

It goes without saying; there are so many more applications for the Applicative pattern out there, I hope you find them and recognize them!

And that concludes the penultimate part of this series! I hope you're enjoying and are able to keep up, if not, feel free to contact me for clarifications. I hope you learned something new, and see you in the last part The Monad!

Reference: https://en.wikibooks.org/wiki/Haskell/Applicative_functors