The Culmination: Part II
That’s right, [I said it][culmination-i]. Monads. The boogeyman of functional programming; the impenetrable concept; the arcane mathematical chimera that Haskell programmers swear by while the rest of the world rolls their eyes. I even said that it had something to do with the future of Swift—which of course I can’t possibly know since I don’t work for Apple, but which I decided to fear-monger with anyway.
The truth is, if you’ve come with me this far, you’re almost there with monads. There’s not that much more to them than >>=-—it’s the foundational operation. The rest, what I’m going to cover in this post, is for support and guidance—it’s to make them nice and useful and friendly. It’s to make you like them. And to prove that to you, I’m going to start by solving (with Magical Future Swift) the problem of unwrapping multiple optionals.
• • • • •
Birthday Beth has invited three friends to her party. If all three show up, she plans to have a super-fun game that involves all three of them; otherwise, just a regular game. Since she’s also a Swift developer, she wants to encode her logic in a function:
func partyTypeForFriend(friend1:Friend?,
friend2:Friend?,
friend3:Friend?) -> Game {
if let f1 = friend1 {
if let f2 = friend2 {
if let f3 = friend3 {
return Game.Superfun(f1, f2, f3)
}
}
}
return Game.Regular
}
[So this all seems…horrible.][hulk-arrives] But fortunately, Magical Future Swift allows her to use something called a for-comprehension:1
func partyTypeForFriend(friend1:Friend?,
friend2:Friend?,
friend3:Friend?) -> Game {
let optionalGame = for {
f1 <- friend1
f2 <- friend2
f3 <- friend3
} yield {
Game.Superfun(f1, f2, f3)
}
return optionalGame ?? Game.Regular
}
Doesn’t that look nicer? None of that deep nesting, merely an “assignment” to the unwrapped values that we want, and a yield block that returns the result—if possible. And if one of those ungrateful friends doesn’t show up, a nil-coalescing call at the end. Much cleaner.
• • • • •
Scheduling Sam has a different problem. He wants to schedule chess tournaments in a number of different cities. In each city, there are two teams, and every player from the first team must play every player from the second team. What are the matchups he’s going to need?
func matchupsForCities(cities:[City]) -> [Matchup] {
var matchups = [Matchup]()
for city in cities {
let teamA = teamAForCity(city)
let teamB = teamBForCity(city)
for p1 in teamA {
for p2 in teamB {
matchups += [Matchup(city:city,
player1:p1,
player2:p2)]
}
}
}
}
This is about equally awful. Can Magical Future Swift help? I thought you’d never ask:
func matchupsForCities(cities:[City]) -> [Matchup] {
return for {
city <- cities
p1 <- teamAForCity(city)
p2 <- teamBForCity(city)
} yield {
Matchup(city:city, player1:p1, player2:p2)
}
}
Again, no nasty nesting, just “assignments”. But the semantics have changed: whereas the <- assignments in Beth’s case only happened if there was a Some value, in this case they happen for each element of each list. The yield block then coalesces them together into one giant list. Doesn’t this sound familiar?
• • • • •
For-comprehensions belong to Magical Future Swift because they are new syntax. More specifically, they are syntactic sugar, in the exact same way that ?. is syntactic sugar for various versions of chained optional calls. And yes, as you might have guessed, they are sugar around calls to >>=-, which, if you [recall][understanding-optionals], already provides the foundation for if-let. To show that, let’s rewrite Beth’s birthday conundrum as a series of calls to >>=-:
func partyTypeForFriend(friend1:Friend?,
friend2:Friend?,
friend3:Friend?) -> Game {
let optionalGame =
friend1 >>=- { f1 in
friend2 >>=- { f2 in
friend3 >>=- { f3 in
.Some(Game.Superfun(f1, f2, f3)})
}
}
}
return optionalGame ?? Game.Regular
}
We have two things going on here. First, the nesting of the >>=- calls ensures that each level sees the previous level’s unwrapped variables (f1 in the second level, f1 and f2 in the third). Second, the entire thing returns an optional.2 That explains why the comprehension returned an optional: in effect, each of its lines is a call to >>=- nested in the previous line’s call. Since >>=- returns a type of the original structure, >>=- with an Optional returns and Optional, and the entire comprehension must do the same.
So how does that work with arrays? Here’s the solution to Sam’s problem, rewritten with >>=-:
func matchupsForCities(cities:[City]) -> [Matchup] {
return city >>=- { city in
teamAForCity(city) >>=- { p1 in
teamBForCity(city) >>=- {p2 in
[Matchup(city:city, player1:p1, player2:p2)]
}
}
}
}
We see that the structure is identical to the structure of Beth’s birthday problem, which is why the same syntactic sugar can work, even though the semantics are very different. And like last time, makes perfect sense that the yield block would return a list: it’s what >>=- returns.
• • • • •
So, for-comprehensions help get rid of some of that clutter brought about by optionals, results, and occasionally even arrays. And they’re all made possible through the >>=- function. But what does this have to do with monads?
Well, for for-comprehensions to work, the structures they operate on need to have some reasonable rules, otherwise things break down badly. Those rules are what define a monad. So as we go through the rules, just remember: their most important consequence is that for-comprehensions behave nicely.
Let’s begin with that yield block. Since it’s generic, it must be callable across structures—or, as we should get used to calling them, across monads. If you look at the syntax of the yield blocks above, you’ll notice that they have unwrapped values: there is no optional declared in Beth’s case, and there is no array in Sam’s. However, when we look at the >>=- based implementations, the final result is wrapped. So clearly, yield is doing the job of wrapping the results in the appropriate monad, and the only way it can do that is by calling a function. In Haskell, this process is often called “lifting”, so let’s call the function lift. It’s signature must be:
func lift<A>(val:A) -> M<A>
M here is our monad of choice. So we have to have two functions defined for our two cases to work:
func lift<A>(val:A) -> [A] { return [val] }
func lift<A>(val:A) -> A? { return .Some(val) }
So Beth’s syntactic-sugar-free code, using lift, becomes:
func partyTypeForFriend(friend1:Friend?,
friend2:Friend?,
friend3:Friend?) -> Game {
let optionalGame = friend1 >>=- { f1 in
friend2 >>=- { f2 in
friend3 >>=- { f3 in
lift(Game.Superfun(f1, f2, f3)})
}
}
}
return optionalGame ?? Game.Regular
}
The same can be done with Sam’s, and now the code will be completely generic, and thus completely amenable to syntactic rewriting.
So if a >>=- implementation is our first requirement for a monad, a lift implementation is our second. Every monad must define lift so that the yield block can work properly.
• • • • •
What does “work properly” mean? How do >>=- and lift interact? Look at this snippet:
let a = 1 // situation 1: a is a regular Int.
let optB = Optional.Some(1) // situation 2: b is an Optional.
// log(val:Int) -> Float? — returns .None if val <= 0
let c = log(a)
let d = for {
b <- optB
e <- log(b)
} yield {
e
}
You wouldn’t write this particular comprehension, but it definitely works. In the code above, c == d. With the definition of lift that we have for optionals, we can rewrite optB and get the same result:
let optB1:Int? = lift(a)
let d1 = for {
b1 <- optB1
e1 <- log(b1)
} yield {
e1
}
Rewriting that in >>=- terms, we have:
let d1 = lift(a) >>=- { b1 in
.Some(log(b1))
}
It turns out this is an important property that we can generalize to all monads. For any function f: A -> M<A>, this is what it looks like:
let a = … some value
lift(a) >>=- f == f(a)
This is the first monad law. It’s a fundamental sanity-check, and ensures consistent behavior of for-comprehensions with different monads.
• • • • •
Along the same lines, there’s another situation that we want to make sure works fine. Consider this snippet:
let arr:[A] = … // some array
let a = for {
b <- arr
} yield {
b
}
Clearly, arr should be the same as a, since the yield block is doing nothing to the value. However, rewriting this in terms of >>=-, we get:
let a = arr >>=- { b in
lift(b)
}
Rewritten, this means that:
let a1 = arr >>=- lift
a == a1 // evaluates to true
For-comprehensions behave sanely only if we guarantee this always holds; we therefore make it the second monad law. And incidentally, this is the law that the second implementation of >>=- for arrays [in my previous post][culmination-i-alternative-bind] fails. That’s why I could say that the first implementation is better.3
• • • • •
Now we’re getting somewhere with this whole monad concept! Informally, monads can be thought of as entities that can be processed in a for-comprehension.
We’re not quite finished, though; there is one last monad law to cover. Given how long this post has become, and given that surely some recap will be in order after completing the monad tour, I’m going to do leave you to digest the first two laws and the new syntax. [My next post][culmination-final] will cover the third monad law—and hopefully crystalize the whole concept in a way that makes sense.
1 I made the decision to go with for-comprehensions (Scala-style) rather than do-notation (Haskell-style) because do-notation would confuse things with the return call. I won’t be covering everything about for-comprehensions, though.↩︎
2 I didn’t avail myself of the auto-creation of optionals that Swift gives us to make it crystal clear that we’re creating an optional. This will be important further down.↩︎
3 “Better” doesn’t mean “only”. As far as I know, there is no proof that >>=- definitions are unique for each datatype, or even just for arrays. However, for a >>=- to work with Magical Future Swift’s for-comprehensions, it must obey the monad laws. I’d be interested if anyone has an alternative implementation that does.↩︎
[culmination-i]: http://nomothetis.svbtle.com/the-culmination-i
[culmination-i-alternative-bind]: http://nomothetis.svbtle.com/the-culmination-i#alternative-bind
[culmination-final]: http://nomothetis.svbtle.com/the-culmination-final-part
[hulk-arrives]: http://www.youtube.com/watch?v=NvY_sMf9b_Q
[understanding-optionals]: http://nomothetis.svbtle.com/understanding-optional-chaining