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

[Will Fancher]

As a quick addendum, I'd like to point out that implementing Monad, Applicative, and Functor allows for some "free" code reuse. Functor can be defined expressly in terms of Applicative, which can be defined in terms of Monad.

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

    protocol Applicative {
        typealias ApplicativeType
        static func pure(a: ApplicativeType) -> Self
        func apply<
                Func, Return
            where
                Func ~= Self, Return ~= Self,
                Func.ApplicativeType == (ApplicativeType -> Return.ApplicativeType)>
        (f: Func) -> Return
    }

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

    extension Monad: Applicative {
        static func pure(a: MonadType) -> Self {
            return point(a)
        }

        func apply<
                Func, Return
            where
                Func ~= Self, Return ~= Self,
                Func.MonadType == (MonadType -> Return.MonadType)>
        (f: Func) -> Return {
            return f.flatMap { fn in
                return self.flatMap { m in
                    return point(fn(m))
                }
            }
        }
    }

    extension Applicative: Functor {
        func fmap<Return where Return ~= Self>(f: ApplicativeType -> Return.ApplicativeType) -> Return {
            return apply(pure(f))
        }
    }

The effect here is that just defining an implementation of Monad on a type gets Applicative and Functor for "free". Granted, those implementations are far from optimized, but they're free, and can be overridden for optimization. The point is, the higher kinded types in use here drastically reduce repetitive code by allowing common patterns like these definitions of Applicative and Functor to be abstracted.