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

[Dave Abrahams]

> On Dec 16, 2015, at 1:10 PM, Will Fancher <willfancher38 at gmail.com> wrote:
> 
> With respect specifically to Monads, there are numerous useful abstractions. For one, Applicative and Functor can be derived for free, 

This is the “other than implementing the basic HKTs themselves” case I was specifically trying to exclude.  The fact that I can build HKTs on HKTs is not relevant to the question of the usefulness of HKTs for solving the real problems of Swift programmers.

> requiring the no effort on the Monad instance's part. This alone eliminates a lot of code repetition. Additionally, the large majority of functions described for Haskell here are very useful:
> 
> https://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad.html.
> 
> Those functions come as abstractions over monads which can be easily understood (if you understand monads) and which eliminate a lot of code repetition.

I have spent significant hours of my life studying and working with Haskell, Monads, et al., and I still don’t think  these abstractions are “easily understood.”  For example, mapM: "Map each element of a structure to a monadic action, evaluate these actions from left to right, and collect the results.”  

It raises these questions.  Understand please that I’m not asking for the answers to the questions; I know them already (or how to discover them if I want to).  The answers are never either easy or crisp, in my experience.

• What does “element of a structure” mean for an arbitrary monad?  Take the I/O monad for example.  What structure?!
• What is a “monadic action?”  In fact, how can we even talk about “action,” which is a very imperative idea, in a purely-functional context?
• What does “collect the results” mean?

In general, the meaning each of these phrases depends on the specific monad since there is no common semantic basis for the Monad abstraction (other than its laws), only a structural one.  That makes the whole exercise of understanding what a Monad is, what it’s for, and what these functions like mapM mean, a highly circular one.

> The existence of these abstractions makes any Monad type much more robust that it would be on its own.
> 
> There are plenty of typeclasses in Haskell that could be implemented in Swift and would be useful if we had HKTs. Foldables and Traversables, for example, are simple and powerful abstractions that would be well worth having.

What problems would these solve for our users?

> And there are various simpler things besides Haskell typeclasses that can't be done in Swift as it stands. For example, you can't currently take a collection of type C1: CollectionType, and return a value of type C2 where C2 ~= C1, which means you can't perform arbitrary transformations on arbitrary collections. You have to choose an implementation type and use that one.

Yes, it would be nice to be able to represent that constraint, and that’s an HKT thing.  

> This isn't to say this should all be in the standard library. I think most of these protocols would be best off in a separate package, to keep the standard simple for newcomers and for those who don't need these features.

Mmm, I don’t know.  Do you want the map that comes from CollectionType, or the one array will get from its conformance to Monad, which will only be in an extension you load with a separate package?  Shouldn't every CollectionType be a Functor?  I haven’t thought this through deeply but I’d be surprised if it these abstractions can be useful without also being woven into the foundations of the library.

> So I'm not suggesting that the Swift team create Monad, Functor, etc. in the standard library and then extend all the appropriate types to implement those (although it'd be a bonus if the team wanted to). That job would be up to whoever wants to write the package for it. But, in my opinion, the ability for such a package to exist seems very important.

If it’s truly important and general-purpose, I would have no problem putting it in the standard library.  My concern is that it may not be important enough, to enough people, to warrant the attendant language complication.

-Dave