NOTE: I've posted an update at the end based on some of the Twitter

conversations.

Rui Peres asked me for my opinion about a piece he wrote about

Monads, partially the context of Swift. Sure!

I'm by no means an expert in functional programming, so be sure to question all things I say. =) Chris Eidhof knows this stuff much, MUCH better than I do and could probably offer a much different perspective.

So, my thoughts… well. It's more complicated than that. =) It's more complicated because it actually feeds into something I've been feeling for many years and only recently really been trying to understand and figure out if there is something tangible I can do to make it better, if for no one else, at least for myself.

So, general critique of the article: I think it was a fair overview of monads and somewhat of an introduction to functional programming in general. I would have maybe added some mention about monads and their use for capturing side-effects in programs, but that's about it. Oh, and make sure the code samples work and state the version of Xcode the Swift samples work on as that's a moving target.

As for functional programming in general: I think there is a tendency to treat it as a magic bullet for solving many of the problems in computer science. Now, this is not to knock on functional programming in the slightest; I believe that it's a paradigm that can teach us many good things. But like everything, it must be used in proper moderation and with care in order to be truly effective.

When I think of functional programming, I see it as trying to apply some core principles to your code base. I would call these out as:

1. Functional evaluation – everything is a function and should be composable. 2. Clean state – side effects should be scoped to their context.

And that's really it; everything else stems from those two things. Composable functions like map are just a satisfaction of goal #1. Monads are a way to make goal #2 happen. At the end of the day, these are all abstractions.

Here's the thing to remember though: there's no such thing as zero-cost abstractions (slides, video). I'll touch on this a bit more later.

Back to the article… let's look at one of Rui's examples (modified to make Xcode 6.1.1 happy):

public final class Box<T>
{
    let value : T

    public init(_ value : T) {
        self.value = value
    }
}

func flatten<T>(box : Box<Box <T>>) -> Box <T> {
    return box.value
}

func map<T,U>(box : Box<T>, f : T -> U) -> Box<U> {
    return Box(f(box.value))
}

infix operator  >>=  {associativity left}
func >>= <T,U>(box : Box<T>, f : T -> Box<U>) -> Box<U> {
    return flatten(map(box,f))
}

let box = Box(4)
let sum3 = { Box($0 + 3) }
let toString = { Box(String($0 + 0)) }
let iReallyLike = { Box("I really like the number " + $0) }

Each line is perfectly understandable. Each is also fairly near to its most generic abstraction for each case (at least in terms to make Swift happy). But it's the next line that gets me:

let luckyNumber7 = box >>= sum3 >>= toString >>= iReallyLike

These are the questions that I ask myself for most of my code:

1. What does it do? 2. Is it maintainable? 3. Is the performance OK? 4. How about memory usage? 5. Is it safe? 6. Reentrant? 7. Does it need to be?

Now, #1 can be tricky. It's a pretty common convention to define the >>= as composition type operator (or more formally, the bind operator), so it's fairly safe to say what it does without explicitly checking. However, you still need to do so if you really want to be sure.

The basic point of the operator is to take something like this (from an imperative view)¹:

iReallyLike(toString(sum3(box.value).value).value).value

And turn it into the most compostable solution presented above. Granted, if we were not boxing the types we'd simply have:

iReallyLike(toString(sum3(box)))

Of course, if we didn't have the boxed types, well, then we wouldn't have the monads, and that is, after all, the point of the post.

What you need to realize is that a monad is an abstraction. Again, that doesn't make it a bad abstraction.

In the example above, we have multiple considerations to make:

1. How much memory does each Monad copy take? 2. Can the memory be safely shared to reduce the amount of memory necessary? 3. How much function overhead are we actually imposing with every call? 4. Can we write a compiler that is smart enough to know when it is safe to

deconstruct the unwrapping of the monad? 5. If we hit a performance issue, do I have a way that I can make this better

without getting rid of the abstractions? Without making the code difficult to

maintain?

These are just some of the basic questions we need to ask ourselves.

You really should be asking yourself these questions. I feel like we have

regressed significantly as an industry because we've gotten fat and are used

to fast machines with lots of memory. Even our smart phones have gigs of RAM.

Too often we blindly make the trades without even understanding we are doing

it.

Here's an example that I saw recently from an email conversation I was having with another individual about a blog post I had written:

func functionalCount(sentence: String) -> Int {
    let words = sentence.componentsSeparatedByString(" ")
    return words
        .map { countElements($0) }
        .filter { $0 > 3 }
        .reduce(0, combine: +)
}

The purpose was to count the number of characters in all of the words that had more than three characters in them. Now, maybe this is a naïve approach to writing this solution, but it is a straight-forward implementation of using the individual components to glue together a solution.

Here's the same, basic algorithm in the imperative form:

func imperativeCount(sentence: String) -> Int {
    var count = 0
    let words = sentence.componentsSeparatedByString(" ")

    for word in words {
        let characters = countElements(word)
        if characters > 3 {
            count += characters
        }
    }

    return count
}

The rough timing and memory estimates I did showed basically a 2x improvement for the imperative version and a 70KB memory reduction. The sample text was 10 instances of the Gettysburg Address. I'm sure we could spend a good deal of time fine tuning the performance of each of them. But, if we are in somewhat of an agreement that this is idiomatic code for the two styles, it's a fair question to ask: what's the point of the functional version and is it inherently better?

Here's my high-level, meta point: the functional version doesn't offer any intrinsic value at understanding the problem as a whole. In fact, both are really just a means to the same end: counting those characters.

Update: January 19th, 2015

I received a bit of feedback on Twitter, and since Twitter is a terrible place to actually have a conversation of any substance, I'll put my replies here.

First off, I'm not surprised to see the recommendations for improvements to the functional implementation. While that misses the point somewhat, especially since that code was not mine to begin with, I'll make the updates so we can see some of the potential benefits.

func lazyFunctionalCount(sentence: String) -> Int {
    let words = sentence.componentsSeparatedByString(" ")
    return reduce(
        lazy(words)
            .map { countElements($0) }
            .filter { $0 > 3 },
        0, +)
}

This is faster than the initial version, and essentially the same memory footprint as the imperative version. I'd argue that readability has suffered though.

Next, my "imperative" version wasn't really all that imperative. I agree. But that is one of the points of the article: we should let the good ideas of the functional world flow back into the imperative world. I think that a synergy can be had when we merge the two instead of attempt to stay wholly in one of the realms.

Rob Napier mentions that "Binding (as in for-in) rather than storing vars is the heart of FP. Bind vs. store is the whole argument." I agree with that. I think another way of looking at it is in the context of "what languages" vs. "how languages". I think there is great value in expressing your logic as a description of what you want to do instead of how you want to do it.

Take for example this imperative approach to the problem:

func reallyImperativeCount(sentence: String) -> Int {
    var count = 0, size = 0
    let utf16 = sentence.utf16

    for var idx = utf16.startIndex; idx != utf16.endIndex; idx++ {
        let c = utf16[idx]

        if c == 32 {
            if size > 3 {
                count += size
            }
            size = 0
        }
        else {
            size++
        }
    }

    if size > 3 {
        count += size
    }

    return count
}

This is ugly… but boy is it fast. About 26x faster than the initial imperative solution. The above solution tells you the "how to do it" and has lost much of the "what to do". It's also error-prone; I had to spend about 10 minutes tracking down a couple of bugs in this implementation that were gracefully handled in the other two solutions above.

But I think this illustrates one of my main points: abstractions have a cost. It's not always important to write the truly imperative solution above, but when it is necessary, it should be possible, and preferably, fit into the same domain space as the original problem and not feel foreign in the language.

1. Yeah, yeah. The bind operator is for transferring one monadic value

   to another monadic value via a function that takes the non-monadic

   value as a parameter. ↩