Higher Kinded Types (Monads, Functors, etc.)

While I agree that showing practical examples - especially used in production code, within the context of a team - is definitely an excellent way to generate pressure towards the addition of native, HKTs in Swift, but I disagree that these encodings should only be buried in a library.

I would accept (and actively contribute to) a library that unifies and standardizes a generic encoding of emulated HKTs in Swift, but I would then use that in my code, to solve practical problems: that's the only way I can really explore abstract concepts and find (and communicate to my collaborators) their utility.

In other words, I'd prefer having a library that provided both some ready-made functors to use, and the ability to cook up a new functor in my code, something that can be readily plugged in the existing framework given by the library.

I strongly disagree with the idea that software development should proceed with some elite subset of developers that masks abstractions within libraries with cool-sounding names, while the rest of the community only uses the final product without any notion of the theory behind, and something so basic as HTKs should really be encoded in the language itself. I tried to use in production code an emulated encoding (for profunctor optics) and it resulted in a massive mess of unreadable code: I probably didn't use an optimal solution in terms of readability, but the amount of boilerplate generic parameters just to make the compiler make assertions about the types involved was too much to bear. So I settled on a different encoding for optics, and a lot of code generation.

But I don't want to sound negative towards HKTs emulation: it's a valuable effort in itself. I simply think that it's just a surrogate of the real thing, a temporary substitute that makes sense in a roadmap that includes the eventual addition of the feature at the language level. Also because this way of programming becomes a true rabbit hole, where the insightful developer can discover wonderful structure that was not apparent at first sight, and encode new powerful abstractions.


A little late reply, but I just discovered this thread and wanted to comment on this. flatMap isn't generally renamed to compactMap. In fact, this rename was made because the so-called flat map on collections weren't really a flat map. But Optional.flatMap is.

In general, a flat map is a function that operates on monads and applies a transform that returns a new monad. And instead of returning a doubly nested structure, it "flattens" the result. To put it more simply:

  • Optional.flatMap takes a transform Wrapped β†’ U? but doesn't return U??. It's flattened to U?
  • Array.flatMap (now) takes a transform Element β†’ [U] but doesn't return [[U]]. It's flattened to [U]
  • Result.flatMap would normally flatten Result<Result<U>> to simply Result<U>
  • and so on.

The old Array.flatMap (and Collection.flatMap etc), confounded two unrelated monads into one. It turned an array of optionals into an array with the nil-optioanals unwrapped. That's fundamentally different that all other cases of flatMap, so this β€” and only this β€” version was renamed.


I believe few people are truly too stupid to comprehend some basic FP (or maths). It may certainly be that some people find this mode of thinking to be more readily available to them than others, but with enough effort, I think it can be learned.

In general, "I am too stupid" is a self-fulfilling prophecy. I hear a lot of people say these kinds of things about maths and/or technology but what they often don't realise is that when any mathematician has to read up on some new math they also don't understand everything right away. Highly abstract ideas cannot be comprehended by reading up on them as if you were reading a book of fiction. It requires careful, slow reading, something that needs to be practiced.

I don't want to convince you that you need to understand HKT; I think they are useful (and I think a language should have them, just so it can enable more abstract coding practices that might be useful in some domains), but I don't believe that every app developer needs to know them - it all depends on what you do. But if you are curious, I encourage you to read carefully, not give up because "it looks cryptic", live with the struggle and come back with concrete questions: "You write XY, but I don't understand it because YZ".


Of course you want the ability to conform your own types to a Functor protocol! On the other hand, you probably don't want to have to deal with all of the boilerplate of the HKT encoding every time you do that (I certainly don't!). That is why a library, possibly accompanied by a boilerplate generator, is essential. I'm glad to hear you would be willing to contribute!

This isn't about an "elite subset" as much as it is about those who have motivation and time to work on fundamental building blocks sharing their work. It would be silly for everyone to reinvent the basics and not everyone has time to do so.

A very important principle in Swift is that of progressive disclosure. I believe the best design for a library based on the abstractions and lessons of FP will embrace this principle. This means that users should be able to use the library and derive as much benefit as possible from it without understanding the theory behind it. Of course the library should also support those who wish to dive deeper as well.

Nobody is arguing with you here. In fact, we are working hard to build motivation for adding this feature to the language.

I would be very interested in seeing what you attempted. If you're willing to share, perhaps some of us will have ideas about how to make it work better.

This is a fact of life for working with some of these abstractions. I'm pretty sure Kotlin's Arrow library relies on generation in some places, I believe it is not uncommon in Scala, and even some Haskell libraries rely on boilerplate generation or Template Haskell. It's obviously not preferable to need code generation but it's also not a showstopper.

We're all in agreement here! That said, my impression is that language support for HKT is a ways off so it is much to our advantage to push the limits of the encoding in the meantime and make it as pragmatic as possible.


I agree with everything you wrote, but this bit in particular seems to me of utmost importance, other than a very interesting problem to solve. The progressive disclosure approach is maybe the thing I like the most about Swift philosophy.

A path towards "discovering" higher kinded types – similar to how you pass from bare protocols to protocols with associated types and constraints – would be a really interesting one to follow.

About the profunctor thing, I'm going to pm you some code ;).

1 Like

Absolutely. I don't have a lot of time for side projects right now, but the time I do have I am spending on this very problem. My focus is on delivering the benefits provided by a principled approach in a Swifty way without requiring users to understand the details of how those benefits are realized. At the same time, I am also focused on avoiding a closed environment like Elm where users cannot grow into more sophisticated approaches without leaving the tool they are comfortable with behind. I'm excited to see where this leads, but it's a slow process given my limited time.


I don't have any books on such esoteric math subjects. Sadly the wikipedia is very bad at these topics.

Me and math separated after a long liking when I hit partial differential equation. The only explanation my brain found was "this is madness" and shut down forever to math.

Your best bet in that case is to avoid this, and any other thread that delves into the theoretical aspects of functional programming. When HKT's land in Swift, you won't need to worry about them if you don't want to. That's the joy of working in a multi-paradigm language.


Well that is exactly what I fear - That this won't be possible because the std lib gets flooded by fp stuff. The std lib is complicated enough already. I never have seen such convoluted code in my 30 years of coding and wonder what advantage this really brings to the table... After all a simple string implentation is still miles away but we need esoteric fp stuff. Somehow the priorities in Evolution seem to be totally broken.

1 Like

I don't think anyone in the Swift community wants Swift to garner a reputation as being an impenetrable functional language like what happened to Haskell (which I'm not saying is impenetrable, it just has that reputation.) So if HKT do get support in Swift, you're probably not going to need to know the theory behind them, or implement your own. You may use them occasionally from the stdlib or elsewhere. But odds are you might not even know that what you're using is baked in a ton of category/language theory.

1 Like

I'll agree that, personally, I also feel there are current Swift pain points that seem more urgent to address than HKT (something like better Linux support, making SPM more feature-rich, etc...), but that's not a basis to shut down a discussion about HKT, not least of all because those people knowledgeable about and interested in HKT are not necessarily the same people that would in the same time do those other things; plus, nobody's talking about a timeline yet.

However, you can't just throw your hands up in the air at every explanation for HKT you get and then pretend that "you don't understand how they're useful". Either, you really want to know what they can bring to the table, then you'll have to do the work and actually understand what people are writing here (and argue from a position of knowledge). Or, and that's perfectably respectable and fair, you say "I don't care about this and don't need to", but then it would be good form to respect the opinions of people who do care about HKT and trust that they have some valid reasoning for their opinion.


You seem to think this is possible for everybody. It isn't. At least in Germany category theory and similar topics are VERY esoteric stuff only a small percentage of math majors even do. It's very hard to get books on this topics normal people would have any change of understanding. I have 2 math doctors in my department but neither of them ever had anything about this stuff. So how are normal coders supposed to learn this stuff?

I don't think that fear is justified. I understand that one of the main concerns of the core team is to make the standard library small: even if we had HKTs in Swift, the stdlib changes would be minimal, and there certainly would not be a functor protocol or something like that. This discussion is really about adding a feature to the Swift type system, and not code to the standard library.

The complications in the standard library are mostly related to the concept of protocol-oriented programming, and the possibility in Swift to write protocol extensions, that actually allow for a lot of code reuse and implementations that are only dependent on specific abstractions (something that follows very well the interface segregation principle).

First of all, no formal training in category theory is necessary to understand the concept of HKT or e.g. functors. If you do understand some CT, it can help, but it is by no means a prerequisite IMHO. Second, if you really do want to learn about CT, there are accessible books available online (e.g. here). Again: I don't think that's a requirement.

1 Like

Thx will have a look at it.

Edit: Result after the first 10 pages - headache. This is approachable?

I've always had trouble with Higher Kinded Types as well. I don't know why. I know I've often gone down meta programming rabbit holes, found I cannot express certain things the way I wanted to, and on occasion been told that those things could be expressible if we had HKTs. Even having done that, I still don't entirely "get" them, I guess.

I might be very wrong here, but my rough understanding is that HKTs would enable you to write something like filter in such a way that the return type would always be correct for your type. As I understand it, the fact that Dictionary's filter returns a Dictionary is because an implementation was added directly to Dictionary to do that.

If we had HKTs, I believe an implementation for filter might be possible to implement as an extension on Sequence and it'd work for everything - even dictionaries - because with HKT support it would know how to 'map' or 'transform' the container's content so that it performs a filter without it having to care what the container actually is and it'd still return the right result type without having to implement one or two or three other versions of filter for different container types just so the return value is correct.

1 Like

A structure-preserving filter doesn't need higher-kinded polymorphism: the component types of the collection don't change, so the operation can just return Self. You need higher-kinded polymorphism to express structure-preserving operations that do change component types, like map, so that you can say that e.g. map: <S<_>, T, U> where S<T>: Sequence, S<U>: MutableCollection (S<X>, (T)->U)) -> S<U>. But that itself prompts several new questions:

  • First, that signature is still restrictive because not all collections are applications of generic types to a single type argument; this supposedly more-generic solution still wouldn't work for BitVector or Dictionary. Some languages solve the second issue by currying everything at the type level, so that their equivalent to Dictionary<K,V> is actually something more like Dictionary<K><V>. That is not how Swift thinks of generics, though, and it would mean that map on Dictionary implicitly only maps the values, not key-value pairs.

  • Second, it's not obvious that map should preserve structure. A lot of possible mappings lose structure in ways that at the very least demand arbitrary rules to resolve. For example, mapping the key-value pairs of a Dictionary and producing a Dictionary can cause conflicts in keys; it matters which entry "wins", but the obvious resolution rule (first entry wins) is problematic because the sequence-order of a Dictionary is unspecified. A similar problem happens with Sets whenever equal values are not completely interchangeable. A map on an ordered set is almost certainly not an order-homomorphism; should the resulting values be reordered in order to create an ordered set, or should it just produce a neutral collection (like Array) in the original order?

There is a fairly common phenomenon in PL design. People often try to prototype their ideas in a certain way, and they find they can't because of the restrictions of the type system. What they remember from this is invariably that the type system is too limited and that they couldn't do what they wanted; which is to say, they assume that their prototype would have worked if only the type system hadn't gotten in their way. But when they are able to implement their prototypes, they often find that their highly-generalized abstractions are less useful than they think, or that they have major semantic drawbacks that they hadn't considered before, and so they find a better way of expressing their ideas that has fewer of these problems. So all the work done in the language to support the new generalization is now only supporting an abandoned prototype, until the next person comes along and needs to re-learn all the same lessons.

For example, you don't need higher-kind polymorphism to do monads in Swift; you need higher-kinded polymorphism to write utilities that are polymorphic over monads. Most such utilities in my experience are just steps in the never-ending march of sugary forms of bind; at any rate, they are easy to duplicate when actually necessary; and I don't even want to talk about monad transformers.


John's post above is really phenomenal. Even if you don't agree with it, it is really useful food for thought.

We (as in the swift-evolution) project should really have a way of highlighting and aggregating great posts like this a centralized way to draw out specifically insightful/interesting contributions. There are a few examples that are commonly back referenced, and it would be great for there to be an analog to the "commonly rejected" list that is "important points to consider" w.r.t common topics like HKTs and other things of historical interest.


Do you understand the Unicode spec in its entirety? Do you still using String?