In my last post I took a piece of imperative code for parsing a comma separated string and generating an instance of a structure, and turned it into a functional piece. At the end we had a bunch of functions that related to code working with Optional, some related to Array, and a bunch that dealt with the actual application code. The "top level" functions we've written looked like this:
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 f = splitter >=> lift(blanker) >=> sequence >=> exactlyTwo >=> build
return f(data)
}
As a bonus, and I can't believe I didn't spot this before, we can change this to:
func createMyRecord(fields: Array<String>) -> Optional<MyRecord> {
let field1Value = fields[0]
let field2Value = lift(stringToInt)(fields[1])
return .Some(createMyRecord) <*> field1Value <*> field2Value
}
let build = splitter >=> lift(blanker) >=> sequence >=> exactlyTwo >=> createMyRecord
This is much much nicer IMO: we've removed an unnecessary function declaration with a constant that happens to be a function.
The issue I have with this, though, is that if there is a problem, one of the fields being invalid for example, then what is returned is None and we have absolutely no clue as to why. It would be better if the code could tell us, so let's look at that.
As before: the full source of this post is available in the file below.
The Optional type can be seen as either success, in Some, or failure, in None. What we'd like is for None to actually give us some information, maybe in the form of an error message as a string. To do this we have to consider Some and None to be two sides of the same type, and so we could try this:
enum Either<L,R> {
case Left(L)
case Right(R)
}
It's either Left(L) or a Right(R). To be able to be consistent we'll say that Right represents success and Left failure because, as the section title says: Left is not Right.
But there's a hitch: Swift doesn't like enums with generic payloads (the Left and Right above) so we have to fiddle things. This means that we have to introduce a Box class that will help use out but unforunately adds complexity to the code that works with the contained values (although this will be hidden). So, our final Either definition is:
class Box<T> {
let value: T
init(value: T) { self.value = value }
}
enum Either<L,R> {
case Left(Box<L>)
case Right(Box<R>)
}
So instead of returning Optional<T> results from our functions, how about we return Either<String,T>? To help with this I'm going to define two functions:
func success<A>(value: A) -> Either<String,A> { return .Right(Box(value: value)) }
func failure<A>(error: String) -> Either<String,A> { return .Left(Box(value: error)) }
Now I can take the function that took a string and returned a UInt if possible, and get it to tell us what was wrong if it couldn't:
func stringToInt(value: String) -> Either<String,UInt> {
if let i = value.toInt() {
if i >= 0 {
return success(UInt(i))
} else {
return failure("The number \(value) is negative")
}
} else {
return failure("The string '\(value)' is not a number")
}
}
It's obvious from this code what is happening, what is an error, and why. We can apply the same logic to exactlyTwo:
func exactlyTwo(values: Array<String>) -> Either<String,Array<String>> {
let size = countElements(values)
if size == 2 {
return success(values)
} else {
return failure("There were \(size) elements and we expect only 2")
}
}
And we can do the same for blanker as, if you remember, blank fields were not ignored, they were errors. Only having None, however, sort of hid that from us:
func blanker(value: String) -> Either<String,String> {
return (value == "" ? failure("We do not accept blank fields") : success(value))
}
Cool! That was pretty painless, unless you've been trying to run this code as I've changed it! In which case you'll appreciate the next section.
Alright, so we have our low level functions returning Either<String,T> now but we need to get our createMyRecord function doing that too. Let's write it as we'd like to:
func createMyRecord(fields: Array<String>) -> Either<String,MyRecord> {
let field1Value = fields[0]
let field2Value = lift(stringToInt)(fields[1])
return success(createMyRecord) <*> field1Value <*> field2Value
}
Can't see the difference? It's pretty subtle but we've changed the return type to Either<String,MyRecord>, as you'd expect, and we've swapped Some(createMyRecord) for success(createMyRecord), which makes sense if you remember that we said Some represented a successful result.
Nothing else has changed. build is remaining the same.
But to achieve this we need to be able to write the various operators and helper functions. Let's start with what I think is probably the simplest: <*>. Quickly let's recap the Optional version of this:
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!")
}
}
If we're working with Either<String,T> then we can take a brute force approach to this: wherever I see None I'm writing either failure or Left, and where I see Some I'm writing either success or Right. Ready?
func <*><A,B>(mf: Either<String,A -> B>, mv: Either<String,A>) -> Either<String,B> {
switch (mf, mv) {
case let (.Left(e), _): return failure(e.value)
case let (_, .Left(e)): return failure(e.value)
case let (.Right(f), .Right(v)): return success(f.value(v.value))
default: assert(false, "Keeping the compiler happy!")
}
}
It's clear what we're saying here: if the function has an error, or the value has an error, then we should return that error; otherwise we return the function applied to the value. The .value calls are us unwrapping the Box values: it's unfortunate that we have to do that's what we have to do.
Alright, what about the associated lift:
func lift<A,B>(mf: Either<String,A -> B>) -> (Either<String,A> -> Either<String,B>) {
return { mv in mf <*> mv }
}
It's now that you should be starting to realise why Swift is no Haskell: Haskell's typeclasses make writing lift easy (you write it once), but Swift needs you to write it over and over again, even though the implementation is the same. It's a shame that Apple couldn't have brought that to Swift too but at least we're practicing!
I'll leave the Either<String,T> versions of the other operators (>>= and <->), along with their associated lift functions, to you dear reader. Or you can skip the to source at the end of this gist!
We're giong to need to do >=> too, but it's only to update the signature:
func >=><A,B,C>(mf: A -> Either<String,B>, mg: B -> Either<String,C>) -> (A -> Either<String,C>) {
return compose(mf, lift(mg))
}
Another win for Haskell.
Our sequence function does need some work though but we follow same Some-Right, None-Left rules:
func sequence<A>(values: Array<Either<String,A>>) -> Either<String,Array<A>> {
func reducer(memo: Either<String,Array<A>>, value: Either<String,A>) -> Either<String,Array<A>> {
switch (memo, value) {
case let (.Left(e), _): return failure(e.value)
case let (_, .Left(e)): return failure(e.value)
case let (.Right(m), .Right(v)): return .Right(m.value + [v.value])
default: assert(false, "Keeping the compiler happy!")
}
}
return reduce(values, success([]), reducer)
}
So at this point you're probably hoping for everything to work but actually we hit number of problems, which all stem from the shorthand optional support in Swift. Essentially we have a number of issues that start in the build code, so let's recap the Optional versions and work from there:
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 f = splitter >=> lift(blanker) >=> sequence >=> exactlyTwo >=> build
return f(data)
}
Our first issue is that the build(Array<String>) function is working with fields that are strings but the code itself is working with the concept that they are Optional<String>: you can see this because of the call to lift and the use of <*>. When we switch this to Either<String,T> it doesn't like lift(stringToInt)(fields[1]) because of the signatures:
let lifted: (Either<String,String> -> Either<String,UInt>) = lift(stringToInt)
let value: String = fields[1]
So calling lifted(value) is just not going to work. It doesn't appear in the optional version because Swift can automatically coerce the String to Optional<String> which is just odd, considering you have to explicitly coerce integers and floats between each other. Yes, I appreciate that the latter can lead to loss of precision, but here we have lost something, or maybe gained something we didn't want.
Anyway, we can quickly fix this issue (remember that we renamed this build version to createMyRecord):
func createMyRecord(fields: Array<String>) -> Either<String,MyRecord> {
let field1Value = success(fields[0])
let field2Value = lift(stringToInt)(success(fields[1]))
return success(createMyRecord) <*> field1Value <*> field2Value
}
We can do better by noticing that we don't need to lift stringToInt if we use >>=, but the order of the arguments is awkward, or rather wrong. Yes, I messed up! What I defined as >>= is actually =<< so let's correct that:
func >>=<A,B>( mv: Either<String,A>, mf: A -> Either<String,B>) -> Either<String,B> {
switch mv {
case let .Left(e): return failure(e.value)
case let .Right(v): return mf(v.value)
}
}
func lift<A,B>(f: A -> Either<String,B>) -> (Either<String,A> -> Either<String,B>) {
return { mv in mv >>= f }
}
Now we can write:
func createMyRecord(fields: Array<String>) -> Either<String,MyRecord> {
let field1Value = success(fields[0])
let field2Value = success(fields[1]) >>= stringToInt
return success(createMyRecord) <*> field1Value <*> field2Value
}
We'll come back to this after we fix up the other issue. The next problem starts with the build(String) function so, again, a recap of it and the splitter:
func splitter(value: String) -> Array<String> {
return value.componentsSeparatedByString(",")
}
let build = splitter >=> lift(blanker) >=> sequence >=> exactlyTwo >=> createMyRecord
Again we have the issue that the >=> expects the first argument to be A -> Optional<B> and, as you can see, splitter is not explicitly defined by this. So we have to change that:
func splitter(value: String) -> Either<String,Array<String>> {
return success(value.componentsSeparatedByString(","))
}
This fixes one problem but then highlights another: splitter >=> lift(blanker) has the signature String -> Array<Either<String,String>> but we then want to connect that to sequence with signature Array<Either<String,A>> -> Either<String,Array<String>>. We don't have a way of doing that in our tool box at the moment, and I couldn't find a decent way of doing it in Haskell with my-good-friend Hoogle so I made something up! Here's my handy operator:
infix operator >-> { associativity left precedence 150 }
func >-><A,B,C>(mf: A -> Either<String,Array<B>>, mg: Array<B> -> Array<Either<String,C>>) -> (A -> Array<Either<String,C>>) {
func lifted(mv: Either<String,Array<B>>) -> Array<Either<String,C>> {
switch mv {
case let .Left(e): return [failure(e.value)]
case let .Right(v): return mg(v.value)
}
}
return compose(mf, lifted)
}
Notice how it handles the failure case in particular: it takes the Left value and puts it into an array. So an error becomes a single element array containing the error. With this we can rewrite our build function:
let build = compose(splitter >-> lift(blanker), sequence >=> exactlyTwo >=> build)
Luckily the order of parameters to compose means that this still reads nicely and, if I could be bothered, I would have created another operator that would do composition.
At this point we should have working code and, if you're in a Swift playground, you'll find that it runs fine. The only problem is you can't actually see what the results are! There are a number of ways around this but I'm going for something that ties into Either: we'll implement a function that, when given an Either, will call one of two functions based on whether the value is Left or Right:
func either<A,B>(failure: (A) -> Void, success: (B) -> Void) -> (Either<A,B> -> Void) {
return { mv in
switch mv {
case let .Left(e): failure(e.value)
case let .Right(v): success(v.value)
}
}
}
Now for our calls we can do:
let debug = either(
{ (e:String) in println("Error: \(e)") },
{ (o:MyRecord) in println("Result: \(o)") }
)
debug(build(""))
debug(build("field1,field2"))
debug(build("field1,2"))
debug(build(","))
debug(build("field1,2,field3"))
And we will find, if you click on the + symbol that pops up on the right side of the playground, that you get a console output of:
Error: We do not accept blank fields
Error: The string 'field2' is not a number
Result: __lldb_expr_210.MyRecord
Error: We do not accept blank fields
Error: There were 3 elements and we expect only 2
So success!
NOTE: I forgot about this bit previously! My bad.
So all through this I've been referring to Either<String,T>: the operators are defined like that, and success and failure are used throughout. But we defined Either to be more generic so we should be able to update our code to be able to handle not only the success and failure, but a more generic left & right. I'm only going to do a couple of these changes as it should be obvious for you what to do with the others.
Let's start with <*> because that'll get us most of what we need to understand:
func <*><A,B,C>(mf: Either<C,A -> B>, mv: Either<C,A>) -> Either<C,B> {
switch (mf, mv) {
case let (.Left(e), _): return left(e.value)
case let (_, .Left(e)): return left(e.value)
case let (.Right(f), .Right(v)): return right(f.value(v.value))
default: assert(false, "Keeping the compiler happy!")
}
}
Here I've replaced String by a new generic C and swapped our failure and success for left and right. These two functions are easy to write and can be used in the former two:
func left<A,B>(value: A) -> Either<A,B> { return .Left(Box(value: value)) }
func right<A,B>(value: B) -> Either<A,B> { return .Right(Box(value: value)) }
func success<A>(value: A) -> Either<String,A> { return right(value) }
func failure<A>(error: String) -> Either<String,A> { return left(error) }
Now we can repeat the String for C replacement throughout most of our code but there are a couple of places we have to think laterally:
func >=><A,B,C,E>(mf: A -> Either<E,B>, mg: B -> Either<E,C>) -> (A -> Either<E,C>) {
return compose(mf, lift(mg))
}
func >-><A,B,C,E>(mf: A -> Either<E,Array<B>>, mg: Array<B> -> Array<Either<E,C>>) -> (A -> Array<Either<E,C>>) {
func lifted(mv: Either<E,Array<B>>) -> Array<Either<E,C>> {
switch mv {
case let .Left(e): return [left(e.value)]
case let .Right(v): return mg(v.value)
}
}
return compose(mf, lifted)
}
Because C was already being used I switched for E, I guess because it reminded me that this was probably an "error"!
A lot: functors, applicatives, monads, swift, operators. The biggest two things I've got from this are:
- Functional techniques that sound obscure and hard to understand aren't if you can find a decent way to work from where you are (for me that's a slightly imperative brain) to where you need to be. I find it easier to learn if I have a task in front of me than an esoteric and abstract post on something.
- Swift is no Haskell at the moment: introducing a new monad, let's say the dreaded
IO, will mean going through the pain of having to duplicate aliftand the operators<->,>>=,<*>,>=>and>->. Haskell's typeclasses would make this a non-issue, I would expect. Also, Haskell would allow us to useEither<String,T>asError<T>because it's types, as well as it's functions, are curried!
Hopefully you've got something from these posts and I'll probably come back with another: I think I'll be doing State next if it fits some of this code.