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

[Douglas Gregor]

> On Dec 16, 2015, at 3:11 AM, Will Fancher via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 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,

Without going into any specifics of higher-kinded types, I sent out a note last night about what the “Swift 3 Generics” effort entails, here:

	https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002718.html <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20151214/002718.html>

One comment there is that I consider higher-kinded types out-of-scope for Swift 3. There is a *lot* of intended churn in generics already in Swift 3, and we will not be able to handle either the design or the implementation of higher-kinded types as well.

	- Doug

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151216/c19ced77/attachment.html>