I’ve been writing a load of Swift code recently for work and this has lead me into the world of typed functional programming. The app needs to build certain objects from a comma separated string, and this lead me to applicative functors, which lead me to brain ache but enlightenment. So here’s my thoughts on how I got to understand these a little better.
All of the code is in Swift, so less clean than Haskell. I’m also only a about 6 weeks into Swift development so I probably haven’t got all of the idioms right. I’ve avoided the optional shorthand wherever possible here, preferring Optional<Type> over Type? because I believe the latter is hiding something that helps understand this code in the context of other generic classes.
It’s also long! I think it’s probably the longest blog post I’ve ever written but I found it interesting and useful, for myself, to write. If you’re one of those people who skip to the end of a book to find out whodunit then I’ve included the entire source for this at the end of this gist.
Also, please be aware that I've written this post in the way I learned rather than with the knowledge gained from that experience. So there are mistakes in this that you might spot but I didn't when I was learning until I got to the next step. So do keep reading as though you are as naive as I was because I think this experience helps the understanding.
Let’s say that I have a simple structure of two fields:
struct MyRecord {
let field1: String
let field2: UInt
}
And I have a comma separated string: the first value in the string will be ‘field1’, and the second will be ‘field2’. If either of these fields is empty then we should not build a MyRecord instance; if the string cannot be split into exactly two fields we should not build a MyRecord instance; if the ‘field2’ value in the data cannot be turned into an UInt we should not build a MyRecord.
Imperatively here’s some code:
func build(data: String) -> MyRecord? {
let fields = data.componentsSeparatedByString(",")
if countElements(fields) != 2 {
return nil
} else if fields[0] == "" {
return nil
} else if fields[1] == "" {
return nil
} else {
let field2Value = NSString(string: fields[1]).intValue
return MyRecord(field1: fields[0], field2: UInt(field2Value))
}
}
Arguably this is pretty clean but the processing of the fields is mixed into the decision about whether to build the MyRecord instance.
Let’s start with the simplest thing that we do pretty much every day without thinking about it: mapping a function over a list. What we’re going to do, eventually, is get rid of the checks for blank fields by making those fields nil initially. We’ll write a function that takes a string and return an optional string that will be nil if the input is blank:
func blanker(value: String) -> Optional<String> {
return (value == "" ? .None : .Some(value))
}
I’m electing here to use the long hand version of optional values in Swift: I could have written Optional<String> as String? but I feel, for this post, that it would hide the details of what it is to be optional. I’m also choosing None and Some for the same reason: None is nil and Some would just be the value.
Now we can apply this function over a list of strings and make our function a little more “functional”, barely:
func build(data: String) -> Optional<MyRecord> {
let fields: [Optional<String>] = map(data.componentsSeparatedByString(","), blanker)
if countElements(fields) != 2 {
return .None
} else if let field1Value = fields[0] {
if let field2 = fields[1] {
let field2Value = NSString(string: field2).intValue
return MyRecord(field1: field1Value, field2: UInt(field2Value))
} else {
return .None
}
} else {
return .None
}
}
Notice that we’ve not really gained anything and that we’ve become a little encumbered by the nesting; I’ve also switched the optional values to the long hand version here too, just for consistency. Although this might seem a step backward it highlights something that we’ll come to in a minute that is hidden by the nature of Swift, IMO.
From the imperative perspective, map applies a function across a list of values, as I myself described it earlier; however, from the functional perspective we can view it in a different manner: it takes a function and “lifts” it into a function that will apply across lists. It’s not obvious from map because of how that function is defined but we can create another function called lift:
func lift<A,B>(f: A -> B) -> ([A] -> [B]) {
return { mv in
return map(mv,f)
}
}
The function signature looks unobvious but, if you look past this, all it’s doing is reversing the arguments to map. The signature is actually taking a A -> B, our blanker for example, and returning an [A] -> [B]. So we can rewrite a bit of our build function:
func build(data: String) -> Optional<MyRecord> {
let fields: [Optional<String>] = lift(blanker)(data.componentsSeparatedByString(","))
if countElements(fields) != 2 {
return .None
} else if let field1Value = fields[0] {
if let field2 = fields[1] {
let field2Value = NSString(string: field2).intValue
return MyRecord(field1: field1Value, field2: UInt(field2Value))
} else {
return .None
}
} else {
return .None
}
}
Keep lift in mind as this “lift” concept will keep coming back!
Let’s do this for another piece: taking a string a returning the integer value.
func stringToInt(value: String) -> Optional<UInt> {
return .Some(UInt(NSString(string: value).intValue))
}
This looks like our blanker function so if we had a list of strings we could “lift” it using lift. However, what about if we have an optional string: could we “lift” it to work with that? In fact you can. Let’s start by rewriting the lift signature we have so we can squint at it a bit and see the leap-of-faith you have to take:
func lift<A,B>(f: A -> B) -> (Array<A> -> Array<B>) {
return { mv in
return map(mv,f)
}
}
All I’ve done is swap the short hand [A] for the long hand Array<A>. Now, what we’d like is a function that would work for optional values, so why not simply replace Array for Optional and rewrite the contents of lift to “do the right thing”? What’s the “right thing? Well, if the value that is passed in to our lifted function is None then we should return None, otherwise we’ll return the result of applying our function f:
func lift<A,B>(f: A -> B) -> (Optional<A> -> Optional<B>) {
return { mv in
switch mv {
case .None: return .None
case let .Some(v): return .Some(f(v))
}
}
}
So we can apply this to our stringToInt function right? Well, no: stringToInt is a function with signature String -> Optional<UInt> and, if we follow the types in our lift above, we’d lift it to Optional<String> -> Optional<Optional<UInt>>. A what now? An optional value that is itself an optional unsigned integer. Yeah, that’s not right! What we really need is an lift that takes an A -> Optional<B>:
func lift<A,B>(f: A -> Optional<B>) -> (Optional<A> -> Optional<B>) {
return { mv in
switch mv {
case .None: return .None
case let .Some(v): return f(v)
}
}
}
What’s the difference in the implementation? The fact that when the input is some value we don’t wrap the result of applying f in a Some, because we don’t need to: the function f has the logic about whether it should. Now we’re going to stick with it and rewrite a small part of our build function:
func build(data: String) -> Optional<MyRecord> {
let fields: [Optional<String>] = lift(blanker)(data.componentsSeparatedByString(","))
if countElements(fields) != 2 {
return .None
} else if let field1Value = fields[0] {
if let field2Value = lift(stringToInt)(fields[1]) {
return MyRecord(field1: field1Value, field2: field2Value)
} else {
return .None
}
} else {
return .None
}
}
This is starting to look a little better and, hopefully, the next bit will start to really have an affect.
What we’ve done so far is written two versions of lift and I’ve craftily ignored the section titles. But let’s list their signatures:
(A -> B) -> (Optional<A> -> Optional<B>)
(A -> Optional<B>) -> (Optional<A> -> Optional<B>)
If you think carefully about these lift functions there are three other possibilities:
(Optional<A> -> Optional<B>) -> (Optional<A> -> Optional<B>)
(Optional<A> -> B) -> (Optional<A> -> Optional<B>)
Optional<A -> B> -> (Optional<A> -> Optional<B>)
The first is boring; the second is weird, and I’m not even sure what that’s representing! However, the latter one will be extremely useful if we carefully refactor a small piece of the build function: we’ll write a function that does what the MyRecord constructor does:
func createMyRecord(field1: String)(field2: UInt) -> MyRecord {
return MyRecord(field1: field1, field2: field2)
}
Note that createMyRecord is curried because that’s important. Rewriting build we now have:
func build(data: String) -> Optional<MyRecord> {
let fields: [Optional<String>] = lift(blanker)(data.componentsSeparatedByString(","))
if countElements(fields) != 2 {
return .None
} else if let field1Value = fields[0] {
if let field2Value = lift(stringToInt)(fields[1]) {
return createMyRecord(field1Value)(field2: field2Value)
} else {
return .None
}
} else {
return .None
}
}
How would our new lift look? If either the function or the value is None then the result of our lifted function should be None, otherwise we should return the application of the function to the value. So:
func lift<A,B>(mf: Optional<A -> B>) -> (Optional<A> -> Optional<B>) {
return { mv in
switch (mf, mv) {
case (.None, _): return .None
case (_, .None): return .None
case let (.Some(f), .Some(v)): return .Some(f(v))
default: assert(false, "Keeping the compiler happy!")
}
}
}
Our aim here is obviously to apply this new lift to our createMyRecord function so if we consider the type signatures involved we end up with:
createMyRecord(String) -> UInt -> MyRecord
lift(Optional<A -> B>) -> (Optional<A> -> Optional<B>)
So a direct application of this lift would give us a new function:
let liftedCreateMyRecord: (Optional<String> -> Optional<UInt -> MyRecord>) = lift(.Some(createMyRecord))
As we know out fields are Optional<String> we can call this function with the value of the first field:
let nextStep: Optional<UInt -> MyRecord> = liftedCreateMyRecord(fields[0])
But now we are back to an optional function, so we need to lift this again. What we end up with in our build is now:
func build(data: String) -> Optional<MyRecord> {
let fields: [Optional<String>] = lift(blanker)(data.componentsSeparatedByString(","))
if countElements(fields) != 2 {
return .None
} else {
let liftedCreateMyRecord: (Optional<String> -> Optional<UInt -> MyRecord>) = lift(.Some(createMyRecord))
let field1Value = fields[0]
let nextStep: Optional<UInt -> MyRecord> = liftedCreateMyRecord(field1Value)
let liftedNextStep: (Optional<UInt> -> Optional<MyRecord>) = lift(nextStep)
let field2Value = lift(stringToInt)(fields[1])
return liftedNextStep(field2Value)
}
}
Wow! Ugly. But we can do something really cool that will make this loads better, and that’s introduce an operator:
infix operator <*> { associativity left precedence 150 }
func <*><A,B>(mf: Optional<A -> B>, mv: Optional<A>) -> Optional<B> {
switch (mf, mv) {
case (.None, _): return .None
case (_, .None): return .None
case let (.Some(f), .Some(v)): return .Some(f(v))
default: assert(false, "Keeping the compiler happy!")
}
}
This takes the essence of our lift function and does the actual application. With this we can do something pretty amazing to our build:
func build(data: String) -> Optional<MyRecord> {
let fields: [Optional<String>] = lift(blanker)(data.componentsSeparatedByString(","))
if countElements(fields) != 2 {
return .None
} else {
let field1Value = fields[0]
let field2Value = lift(stringToInt)(fields[1])
return .Some(createMyRecord) <*> field1Value <*> field2Value
}
}
That looks so much nicer!
But we’re not finished: we can make more changes that will allow us to reuse what we have already done. Let’s start with a function that will take a list of optional values and make an optional list, returning None if any of the members of the input list are None:
func sequence<A>(values: Array<Optional<A>>) -> Optional<Array<A>> {
func reducer(memo: Optional<Array<A>>, value: Optional<A>) -> Optional<Array<A>> {
switch (memo, value) {
case (.None, _): return .None
case (_, .None): return .None
case let (.Some(m), .Some(v)): return .Some(m + [v])
default: assert(false, "Keeping the compiler happy!")
}
}
return reduce(values, .Some([]), reducer)
}
Armed with this we can make our fields variable a bit more interesting:
func build(data: String) -> Optional<MyRecord> {
let values: Optional<[String]> = sequence(lift(blanker)(data.componentsSeparatedByString(",")))
if let fields = values {
if countElements(fields) != 2 {
return .None
} else {
let field1Value = fields[0]
let field2Value = lift(stringToInt)(fields[1])
return .Some(createMyRecord) <*> field1Value <*> field2Value
}
} else {
return .None
}
}
This looks a little like another step backward again but, as before, we can now look for a function we can lift, except this time the function is the entire block of code inside our outer if statement:
func build(fields: Array<String>) -> Optional<MyRecord> {
if countElements(fields) != 2 {
return .None
} else {
let field1Value = fields[0]
let field2Value = lift(stringToInt)(fields[1])
return .Some(createMyRecord) <*> field1Value <*> field2Value
}
}
func build(data: String) -> Optional<MyRecord> {
let values: Optional<Array<String>> = sequence(lift(blanker)(data.componentsSeparatedByString(",")))
return lift(build)(values)
}
So now we have a build function that takes a single string and builds an optional MyRecord, as well as one that takes an array of strings and does the same. Simpler functions, better reuse.
How about making a function that takes an array of strings and returns an array of strings if there are two elements, or nil if there are not:
func exactlyTwo(values: Array<String>) -> Optional<Array<String>> {
if countElements(values) == 2 {
return .Some(values)
} else {
return .None
}
}
And so we’ll rewrite our build functions:
func build(fields: Array<String>) -> Optional<MyRecord> {
let field1Value = fields[0]
let field2Value = lift(stringToInt)(fields[1])
return .Some(createMyRecord) <*> field1Value <*> field2Value
}
func build(data: String) -> Optional<MyRecord> {
let values: Optional<Array<String>> = sequence(lift(blanker)(data.componentsSeparatedByString(",")))
let fields = lift(exactlyTwo)(values)
return lift(build)(values)
}
The body of the String -> Optional<MyRecord> version is a bit rubbish but we can work on that: what we need is a way of composing functions of the form A -> Optional<B> and B -> Optional<C> to get A -> Optional<C>. Normal function composition would use . but because these have the optional return values we need something a little more fancy:
func compose<A,B,C>(f: A -> B, g: B -> C) -> (A -> C) {
return { v in g(f(v)) }
}
infix operator >=> { associativity left precedence 150 }
func >=><A,B,C>(mf: A -> Optional<B>, mg: B -> Optional<C>) -> (A -> Optional<C>) {
return compose(mf, lift(mg))
}
Armed with this we can remove the lifts and do something a little fancy with our build:
func splitter(value: String) -> Array<String> {
return value.componentsSeparatedByString(",")
}
func build(data: String) -> Optional<MyRecord> {
let f = splitter >=> lift(blanker) >=> sequence >=> exactlyTwo >=> build
return f(data)
}
This makes it quiet scarily clear whats happening: we split, blank, sequence, use exactly two, and finally build.
Sort of, although the issue is not with the masses of code I’ve been talking you through but with the intValue call on a string that isn’t a convertible to a number. But if we use toInt() on the string itself it’s much better:
func stringToInt(value: String) -> Optional<UInt> {
if let i = value.toInt() {
if i >= 0 {
return .Some(UInt(i))
} else {
return .None
}
} else {
return .None
}
}
Now we get the right behaviour:
build(“") // nil
build("field1,field2”) // nil
build("field1,2”) // {field1 “field1”, field2 2}
build(",”) // nil
build("field1,2,field3”) // nil
Look: I specifically left out the complicated talk of functors, applicative functors, and monads; I purposefully left those as headings, giving a bit of a hat tip to what I was trying to convey without ending up having to talk about burritos or spacemen. However, there’s something that you should be able to identify and that’s the relationship between the lift function and the application of a function: the former delays the latter, in some ways. Take our lift and <*> for the Optional case:
func lift<A,B>(mf: Optional<A -> B>) -> (Optional<A> -> Optional<B>) {
return { mv in
switch (mf, mv) {
case (.None, _): return .None
case (_, .None): return .None
case let (.Some(f), .Some(v)): return .Some(f(v))
default: assert(false, "Keeping the compiler happy!")
}
}
}
infix operator <*> { associativity left precedence 150 }
func <*><A,B>(mf: Optional<A -> B>, mv: Optional<A>) -> Optional<B> {
switch (mf, mv) {
case (.None, _): return .None
case (_, .None): return .None
case let (.Some(f), .Some(v)): return .Some(f(v))
default: assert(false, "Keeping the compiler happy!")
}
}
See that duplicated switch statement? Let’s remove it:
func lift<A,B>(mf: Optional<A -> B>) -> (Optional<A> -> Optional<B>) {
return { mv in mf <*> mv }
}
So the lift in this case is delaying the use of <*> by wrapping it in a function. We could write similar operators for each of the other lift variants:
infix operator >>= { associativity left precedence 150 }
func >>=<A,B>(mf: A -> Optional<B>, mv: Optional<A>) -> Optional<B> {
switch mv {
case .None: return .None
case let .Some(v): return mf(v)
}
}
infix operator <-> { associativity left precedence 150 }
func <-><A,B>(mf: A -> B, mv: Optional<A>) -> Optional<B> {
switch mv {
case .None: return .None
case let .Some(v): return .Some(mf(v))
}
}
Notice that <-> is actually <$> in Haskell but Swift gets upset with the $ in the operator. Armed with those operators our three optional lift functions are:
func lift<A,B>(f: A -> B) -> (Optional<A> -> Optional<B>) {
return { mv in f <-> mv }
}
func lift<A,B>(f: A -> Optional<B>) -> (Optional<A> -> Optional<B>) {
return { mv in f >>= mv }
}
func lift<A,B>(mf: Optional<A -> B>) -> (Optional<A> -> Optional<B>) {
return { mv in mf <*> mv }
}
FYI: the first is lift for functors, with <-> being synonymous with fmap; the second is lift for monads, with >>= being called “bind”; and the third is lift for applicative functors, with <*> being "sequential application” according to my good friend Hoogle!
In Haskell we would be able to make these lift functions generic on the type of functor/applicative/monad they were operating on but unfortunately Swift doesn’t support this (or at least I couldn’t figure out a way to do it). What this means is that our lift for the array type has to be specifically written with a specific <-> implementation:
func lift<A,B>(f: A -> B) -> (Array<A> -> Array<B>) {
return { mv in f <-> mv }
}
func <-><A,B>(mf: A -> B, mv: Array<A>) -> Array<B> {
return map(mv, mf)
}
If you’re interested then I’d suggest writing the other lift versions, along with the >>= and <*> operators.
This has, I hope, been as enlightening experience for you as it was for me; I’ll even admit that I’ve realised other things whilst writing this post itself. Whilst this implementation of the code is alright I want to revisit this in my next post and deal with error handling: at the moment we can tell something failed but not what. I'll also address those mistakes in the code.