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

[Matthew Johnson]

> On Dec 16, 2015, at 6:26 PM, Dave Abrahams <dabrahams at apple.com> wrote:
> 
> 
>> On Dec 16, 2015, at 4:04 PM, Matthew Johnson via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> 
>>> With higher-kinded types, one could potentially [*] produce a collection of the same kind as Self but with the element type T. So, mapping a Set produces a Set, mapping an Array produces an Array, etc. 
>> 
>> I think structure preserving map is a great example and one I hope will eventually make it into the standard library someday.  
> 
> How, specifically, would you use it?  To which types would it apply, and how would the change benefit users?

A lot of the uses don’t necessarily require HKTs as you can get a lot of mileage out of a structure preserving map with code written against the specific type.  For example, we already have structure preserving maps in the standard library for Array, Optional, and ImplicitlyUnwrappedOptional.  

It would be nice if Set and Dictionary also had a structure preserving map today (mapping over values in the dictionary leaving the keys untouched).  I have seen people pick on Set a bit in regards to this because it can't conform the the usual functor laws so I’ll offer an example of using it there.  Imagine we have a set of people and we want to know the set of dates where at least one person has a birthday (maybe to provide an indicator in a UI).  Structure preserving map is exactly what we need and is quite useful even when the semantics are a bit less strict than the mathematical / categorical definition of a Functor.

I think it’s fair to say that types which *implement* the usual HKT typeclasses / protocols are extremely useful when used in a concrete setting.  Even if you can’t express the protocol or conformance directly in the language the concepts and signatures are valuable as a pattern.

Of course in a thread about HKTs I’m sure you’re looking for examples where the code needs to be generic over the structure.  The most common examples I can think of are “do notation” as well as various methods of effect handling and effect composition.  Swift is clearly taking a different (and better IMO) approach to effects at the language level.  

However it doesn’t (yet anyway) offer all of the control over effects that could be useful.  This may be an area where HKTs would be useful although I don’t have a concrete example ready at hand.  I have been thinking about and experimenting with some architectural ideas for managing (iOS) application state, data flow, event flow, etc using inspiration from reader, writer, state, and continuation monads.  I may eventually find examples here, although it is also quite possible that generic use of HKTs won't really necessary.  It’s hard to say for sure as I haven’t spent enough time on this yet.

So I suppose where I land is that I know the patterns that can only be expressed in a language by HKTs are very useful and practical.  The Swift library already implements these patterns in some areas and they are widely useful.  The library should be consistent in application of the HKT patterns it implements (such as structure preserving map).  

Because it is possible (theoretically) to express the patterns directly in the language it makes sense to eventually be able to do that.  If / when that happens all the library would need to do is declare the corresponding protocols and conformances to enable them to be used generically.

I have an intuition that practical uses for Swift programmers (especially library implementers) would emerge but are hard to find without experimentation and experience.  Because we cannot actually use them today we don’t spend too much time thinking about how to apply them in our immediate context so it’s a bit of a catch-22.  Of course this is a pretty weak argument which is why I am in strong agreement that this is not an immediate or high priority.  But I do hope we have the chance to experiment and find practical uses for HKTs in Swift someday.

Matthew