A World Beyond Swift Maps
In this post, I’m going to talk about something we don’t hear much about in Swift: applicative functors. These let us perform some very powerful operations with a minimum of code.
This is using an extended, and simplified, version of the HKT (Higher Kinded Type) framework I introduced last time . We looked at Functors in Swift: to recap, Functors are “containers” (like Sequences such as Array or a LinkedList) which have a superpowered map called fmap that transforms the container’s contents but leaves the container itself intact. Regular map always returns an Array, even if you start with your data in a LinkedList.
In this post, we’ll take this idea further. fmap (and ordinary map in the Standard Library) are great for some things, but certainly limited. For example, what happens when you want to transform a container using a function with more than one parameter? That’s a problem we can solve with applicative functors.
The Code
As before, the code is available in a playground (including some challenges!) and in an XCode project for addition to your own code.
Tainted Data
By way of a motivating example, suppose we are writing a Web application to calculate retirement savings. As this is a public application, we are concerned we may be passed malicious data. One way of handling this is to consider all external web data as tainted (like Ruby does). We then have a clean process to check and mark data as safe.
In Swift, let’s model WebData using an enum:
(The Constructible conformance and the TypeParameter are there because we are using the HKT framework from my last post)
The interesting thing is that tainted data is pervasive — any function where one of the inputs is tainted will have a tainted output (or equivalently, the output of a function is safe only if all the inputs are safe)
So, let’s suppose we have an ordinary function which takes 3 inputs and calculates an output.
Next, we get 3 inputs from the web for this function:
What we want to do is to run the retirement calculation using these inputs; but return a WebData value which is only safe if all of the inputs were safe.
Here’s one way to do that, with a big switch statement. This works, but has big disadvantages: it’s a long function (because there are 3 parameters, there are 2³= 8 combinations to test in the switch); I’ve had to specifically write the function for WebData (whereas the original just used regular Int, Double etc); and I’d have the repeat the exercise for each function I want to use in my application.
However, WebData is an applicative functor — we’ll see what this means in a moment — so instead we can use some helper functions which the HKT framework provides (more or less) for free.
In this case, we’ll use Appl3 from the framework, which applies a function of 3 parameters to a list of 3 applicative functors. With this, I can get the same effect as that long switch statement with a single line of code, and without having to change my original function.
Let’s say we now clean some data:
For those who are fans of the “continuation style” , you can also use this, which allows functions with any number of parameters:
As you can see, this is much more straightforward than unpacking and packing the container WebData yourself. It’s also a technique that can be used on many other types. We’ll see some examples later.
But first, let’s explain Applicative Functors in more detail.
Applicative Functors
An Applicative Functor (or often just “Applicative”) is a type of container (like a Sequence, Array or LinkedList; or WebData — or indeed Optional) which has a couple of special functions, ap and pure. These allow us to:
- First, “peek inside” a list of containers;
- Second, extract the data from each container;
- Third, perform a calculation using the data items as parameters;
- Fourth, wrap up the result back into the original type of container.
You can think of it as a superpowered Functor which allows a “map” with multiple arguments.
Here’s the protocol² requirement for Applicative’s ap and pure , given an applicative functor type P (e.g. Array, WebData, etc) containing data of type A:
- pure gives me a P<A> if I only have an A.
- ap extracts the value a from self ; takes the function f from the applicative parameter; calculates f(a); and stores the result in another applicative.
One thing you may have noticed that the definition only requires a function of a single argument, (A)→B. What about the multi-argument functions I mentioned previously? The power of applicative functors is that you don’t need to worry about them — this will be explained in the Under The Covers section.
Free For You
In order to make any type into an Applicative Functor, all you need to do is mark the type as conforming to the Applicative protocol, and supply the ap and pure functions.
When you do that, you will get quite a few things for free, thanks to the power of Sourcery:
- Definitions of Appl2 , Appl3 and Appl4 which allow you to apply 2-, 3-, or 4-parameter functions to a list of applicative parameters, and do the unwrap/re-wrap for you.
- Definition of ApplReduce which takes a 2-value function like (+) and runs a “reduce” over a list of applicatives, unwrapping each result and wrapping it back in an applicative. We’ll see an example below.
- Definition of Functor — if your type isn’t a Functor already, it will automagically get a Functor (and fmap) definition! (Question: without looking at the code, can you figure out how to use ap and pure to construct fmap for a type?)
- Definition of operator f <¢> p which stands for “apply function f to applicative parameter p” (and return an applicative)
- Definition of operator fp <*> q which stands for “where fp is an applicative wrapping a function, unwrap the function, apply it to q, and return an applicative”
The last two are very useful for chaining applicatives in a functional “continuation style”, and are in fact how the framework operates under the covers. See the “Under the Covers” section for more details.
- …plus, Sourcery will generate ApplicativeTag (and FunctorTag) for you which allow the mechanics to work. I’m not going to discuss these here; you can get more details from the HKT article. Fortunately, you don’t really need to know about them to use the framework.
Let’s try implementing them for WebData:
Here we are switching over the possible cases, and only return a safe result when the inputs are safe³. This is a bit like the “big switch statement” code I wrote at the top of the article, but notice I’m only looking at 4 different possibilities not 8 (why? See the Under The Covers section)
Given these definitions, here’s an example of using ApplReduce to reduce an array of integer WebData by summing up the integers. If any of the integers are tainted, the whole result will be. Clearly this is pretty powerful, and note that I didn’t have to do anything “special” to get ApplReduce to work over WebData — providing ap and pure is sufficient.
Applicatives Everywhere
We can make other things into Applicatives too! For example:
Optionals
Optionals also meet the definition of applicative functor “containers”, with the “contained type” being the thing that’s optional (eg “Int” in “Int?”). Here’s the definition of ap and pure:
And here’s how we might use them:
You might want to try implementing this without the applicative functor; it’s messy! (See the Playground code)
Arrays
Here’s the definition of ap and pure:
And here’s how we might use them:
That this might be a bit surprising: applying a function over arrays returns all the possible combinations of applying the functions to each element of each array. That’s the ‘standard’ definition of Array as an applicative functor; but often you don’t want that: there’s actually a second way of applying a function to a list of arrays, which is what ZipArray does.
“Zip” Arrays
The other way to deal with arrays is to take each array and apply the function elementwise. Eg, if you have a 3-value function g and 3 arrays [a,b] , [c,d] and [e,f]: your resulting array would be [ g(a, c, e), g( b, d, f ) ] . You might be familiar with that as “zipping” arrays; and so the framework provides a ZipArray type which does exactly that:
I’m not showing the definition of ap and pure here, you can see them in the sample code.
As you can see, with Array and ZipArray it’s possible to build some complex operations that it would be difficult to do otherwise: thanks to them both being Applicative Functors.
Under The Covers
This section is not obligatory to read if you just want to use the framework.
I mentioned above that Applicative Functors would work for “any” number of parameters, yet I’ve only shown Appl2, Appl3 and Appl4 for 2- , 3- and 4-parameter functions. What if I want a 5- or 8-parameter function? This is possible, but rather than build it into the Applicative code, I thought I’d show you how to do this yourself using the “continuation style”. This is interesting as it explains more fundamentally how applicative functors actually ‘work’ — the “clever trick” I alluded to above.
In fact, if you trace through the code, you’ll see that Appl2 …Appl4 both ultimately use the “continuation style” in order to implement their functionality.
For instance, Appl2 contains this:
and Appl3 contains this:
(where f is a curried function ; p, q, and r are the input applicative functor parameters lifted to Construct types, e.g. WebData; and <¢> and <*> are custom operators)
The pattern above relies on f being a “curried function”. Currying allows us to “take apart” a function of n parameters, and turn it into n “mini functions” of one parameter each; the result of one “mini function” feeding into the next “mini function” until the last gives the final result. So a function with type
g: (A,B,C) -> D would be curried into f : (A)->(B) ->(C) -> D.
The function curry does exactly this, here’s how it looks for functions with 3 parameters:
If we look at the Appl3 definition above, you may be able to see how this fits together. (f <¢> p) is like feeding just the “A” value into the curried function; so it actually returns a “mini function” of type (B) ->(C) -> D.
Then, the (…<*> q) part — where … means “the result of f <¢>p” — is like feeding the “B” value into the curried function, so that returns another “mini function” of type (C) -> D.
Finally, (…<*> r) feeds in the C value into the curried function, finally returning a value D.
So, if you wanted to use an applicative functor with a 5-parameter function, you can create an Appl5 if you like; or pass in the curried version of your function into the <$> and <*> operators. Like this:
Further Reading
We are getting into some complex ideas here and the excellent expositions by Miran Lipovača of learnyouahaskell really helped clarify these things for me. Bartosz Milewski and his book Category Theory for Programmers was also an excellent guide (and shout out to Tai-Danae Bradley of math3ma.com too) Brandon Williams and Stephen Celis showed me how functional programming could be useful to Swift developers, and Matthew Johnson with the original version of the Higher Kinded Type playground gave me the clue as to how this could actually work.
Next article: Monad Magic
¹I am not covering the obvious point here about why I am carrying out a function on tainted data in the first place — this might be very dangerous! Note that Ruby restricts certain functions on tainted data.
²I actually ‘cheat’ somewhat. Applicative (and Functor), are actually just empty protocols, which trigger Sourcery to generate some boilerplate code. If your Functor type doesn’t contain the ‘fmap’ function, or Applicative doesn’t contain ‘pure’ and ‘ap’, then the Sourcery build will generate an error with a comment indicating what you need to do to fix the problem. I’ll look to improve this over time (eg Swift 4.1 has better capabilities to report errors)
³You’ll notice pure returns a safe value: possibly a bit surprisingly as we’d want to default a new value of WebData to be tainted. This is actually a consequence of the “applicative functor laws” which I don’t really cover here. To see why, try switching it to be ‘tainted’ and see what fails.
