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

[Will Fancher]

Hello,

A potent problem in my experience with Swift has been the lack of a way to generalize code that is repetitive on the basis of higher kinded types. For the uninitiated, higher kinded types are the ability to reason about generic types with their type parameters as variable. For example, the Haskell definition for Functor, and a corresponding definition for Maybe (Haskell's equivalent to Optional)

    typeclass Functor f where
        fmap :: (a -> b) -> f a -> f b

    instance Functor Maybe where
        fmap f (Just a) = Just (f a)
        fmap f Nothing = Nothing

This makes it possible to build functions which operate not just on Maybe, but on any Functor.

    fstrlen :: Functor f => f String -> f Int
    fstrlen fstr = fmap length fstr
    
    > -- In the Haskell REPL
    > fstrlen (Just "Hello") -- prints "Just 5"

In Swift, such an abstract function is not possible. There simply is no way to express that your function would like to accept a type that wraps something, and returns that same type wrapping something else.

I propose a new where clause in Swift's generics system that would allow for higher kinded type equality. The syntax would be some operator meant to appear to say "like" or "approximately equal", such as ~=. This operator would mean that the two operands are the same type, but with potentially different type parameters / typealiases. As an example, Functor could be implemented like this:

    protocol Functor {
        typealias A
        func fmap<FB where FB ~= Self>(f: A -> FB.A) -> FB
    }

The map function declaration says

    A function, fmap, on the Self type (where Self is a Functor with typealias A)
    With type parameter FB, that is the same kind of Functor as Self, with an arbitrarily different A typealias.

This ensures at the type level that given a Functor f, calling f.fmap will result in the same type of Functor. For example, here is both an implementation of Functor, as well as a function which uses a Functor

    extension Optional: Functor {
        func fmap<Mapped>(f: Wrapped -> Mapped) -> Mapped? {
            if let wrapped = self {
                return f(wrapped)
            } else {
                return nil
            }
        }
    }
    
    func fstrlen<
            FString: Functor, FInt
        where
            FInt ~= FString, FString.A == String, FInt.A == Int>
    (str: FString) -> FInt {
        return str.fmap { $0.characters.count }
    }

As another example, the infamous Monad. Monads are everywhere. Countless data types can be expressed as Monads. It is useful to have an abstraction over them, as it provides a means to implement common operations on all of them without repetitive code.

    protocol Monad {
        typealias A
        static func point(a: A) -> Self
        func flatMap<MB where MB ~= Self>(f: A -> MB) -> MB
    }

A function which is relatively useful, join, can be implemented like this:

    func join<M: Monad, MM where MM ~= M, MM.A == M>(mm: MM) -> M {
        return mm.flatMap { $0 }
    }

There's a whole host of functions and theories that higher kinded types enable. This proposal fits nicely with Swift 3's goal of completing generics, and as far as I can see, there are no obvious conflicts with the Swift language. I imagine the implementation might be far from trivial, but that sounds like a discussion worth having.

I look forward to your feedback. Thank you for reading,

- Will Fancher