[swift-evolution] [Proposal] Higher Kinded Types (Monads, Functors, etc.)

[Will Fancher]

I mentioned several examples in passing, but I suppose I could flesh one or two out.

Futures are a concept used in a lot of web development frameworks as a method of asynchronously representing a value that doesn't exist, but eventually will. Naturally, you represent this with the type Future<T>. You make a Promise<T> object, then pass around and use the associated future values. Here's a very quick example code.

    public class Promise<T> {
        private var handlers: [T -> ()] = []
        private var completed: T? = nil
        
        public init() {
        }
        
        private func onComplete(handler: T -> ()) {
            if let completed = completed {
                handler(completed)
            } else {
                handlers.append(handler)
            }
        }
        
        public func complete(t: T) {
            completed = t
            for handler in handlers {
                handler(t)
            }
            handlers = []
        }
        
        public var future: Future<T> {
            return Future(promise: self)
        }
    }

    public struct Future<T> {
        private let promise: Promise<T>
        
        private init(promise: Promise<T>) {
            self.promise = promise
        }
        
        public func onComplete(handler: T -> ()) {
            promise.onComplete(handler)
        }
    }

Using this, you can create a promise, return its future, complete that promise asynchronously, and be sure that any number of arbitrary handlers definitely get called with the completed value.

    let future: Future<SomeType> = someFutureCalculation()
    future.onComplete { someValue in
        doThing(someValue)
    }

But what about transforming those values outside of the handler, in the context where you received the future? This is where Monad, Applicative and Functor come in.

    // Monad

    public extension Future: Monad {
        public static func point<T>(t: T) -> Future<T> {
            let promise = Promise<T>()
            promise.complete(t)
            return promise.future
        }
        
        public func flatMap<U>(f: T -> Future<U>) -> Future<U> {
            let uPromise = Promise<U>()
            
            onComplete { t in
                f(t).onComplete { u in
                    uPromise.complete(u)
                }
            }
            
            return uPromise.future
        }
    }

Now, we can do interesting manipulations like this

    let future: Future<SomeType> = someFutureCalculation()
    future.flatMap { someValue in
        return otherFutureCalc(someValue)
    }.onComplete { otherValue in
        print(otherValue)
    }

That alone is marginally useful. What's really useful is that if we have the "free" definitions of Functor and Applicative I described in a previous message, we can use those methods by just having implemented the Monad protocol.

    let future: Future<String> = someFutureCalculation()
    future.map(stringToInt).flatMap { i in
        return otherFuture(i)
    }.apply(functionFuture).onComplete { val in
        print(val)
    }

There's a lot going on here, and it comes from free Functor and Applicative definitions that currently aren't possible.

Additionally, if I have been given an array of Futures, I don't have to re-implement sequence to turn that into a Future of an array. I just get this for free.

    let array: [Future<A>] = ...
    let farr: Future<[A]> = sequence(array)

That's super useful.

Having Monads also means that if you would write code which deals with Futures, you can instead write code which deals with Monads or Functors. So this

    func changeFuture(future: Future<String>) -> Future<Int> {
        return future.map { s in
            // create Int from s
        }
    }

can become this

    func changeSomething<FString: Functor, FInt where FInt ~= FString, FInt.FunctorType == Int>
    (functor: FString) -> FInt {
        return functor.map { s in
            // create Int from s
        }
    }

Now, it works with anything, not just Futures.

The point of HKTs isn't to make a specific task easier. The point is that it makes it possible for any types which conform to a HKT protocol to use all the same functions. Thus, you can write a host of functions that operate on HKTs instead of rewriting them for specialized types. In the case of futures, I'd like to remind you that this is all the code it took to make Futures capable of the countless Functor / Monad functions

    public extension Future: Monad {
        public static func point<T>(t: T) -> Future<T> {
            let promise = Promise<T>()
            promise.complete(t)
            return promise.future
        }
        
        public func flatMap<U>(f: T -> Future<U>) -> Future<U> {
            let uPromise = Promise<U>()
            
            onComplete { t in
                f(t).onComplete { u in
                    uPromise.complete(u)
                }
            }
            
            return uPromise.future
        }
    }

Those few lines open up a world of possibilities on the Future type so that I can avoid boilerplate and repetition.