Higher Kinded Types (Monads, Functors, etc.)

@anon27714269 and I have moved this discussion into a private thread to avoid dragging this one off topic. If you’d like to reply, please message me so I can add you there.

As a person that writes mostly functional Swift, and has found in FP a way for improving the correctness, preciseness, safety and simplicity of his code, with actual real-world results that could never be achieved with imperative, impure OO code, I invite everyone that dismisses FP as something pointlessly complex, mind boggling, “cancerous”, to really think about it and at least give the benefit of the doubt to the people that try to use math as a useful tool for writing code. It’s not complex at all, it’s simply hard, but everything is hard at first sight if it’s unfamiliar.

About the topic of HKTs, it would simply be great if Swift had them, it would be a completely additive feature and would improve the life of both application developers and library writers to a gigantic extent. But Swift is still missing a lot of features in its type system that are unrelated to higher-kinded types, but would be useful in day-to-day FP and OO code (like for example generic extensions and a way to specialize generic functions at call site).

Also, @anon27714269, map and filter are not sugar for loops, in the way a class is not sugar for pointers, or a for loop is not sugar for goto, or a variable assignment is not sugar for stack push pull, or code is not sugar for a bunch of 1s and 0s.

11 Likes

Seen it but I can only answer where the question is.

But all of these are syntactical sugar. Perhaps MOS6502 assembler being my first language bites me here?

About map, filter, etc.
There aren't syntactic sugar at least because they do not add any new syntax to the language...

Yes, it bites you. Syntactic sugar is a way to express the same thing more concisely, but map and a for loop express different things.

The programming community made a lot of advancements in the last 5 decades, and Swift should be aware of those: I don't get why anyone would hold back the evolution of a language for no reason, ignoring the thousands of contributions made by the industry and especially the academia in the fields of software development and computation in general. If you can't see this, I can't help you.

Going back to the topic, I've been told in the past by @Chris_Lattner3 that the core team is not against HKTs in principle, but there are more things to get right first. I can understand this, but is the locking of the ABI without considering eventual HKTs a problem?

4 Likes

I am pretty sure we can synthesize appropriate code with what we currently have. That said, even introducing new syntax for HKT’s shouldn’t affect ABI stability. For which the former really holds true, that is.

No, we can’t. In answering your question:

we cannot express what a Functor is with Swift’s current type system, because we cannot (generically) constraint a generic type to be the same concrete type as another type, but with a different specialization.

This is not related to adding a formal algebraic hierarchy to the standard library: we really cannot write a protocol Functor or protocol Monad right now in Swift: we need the ability to express a HKT to actually define protocols like those.

You mean something like this?

protocol Some { associatedtype R }

class Foo<T>: Some { typealias R = T }

Or you mean to universally parametrize the protocol (protocol Some<T>)?


Or are you questioning the importace of Optionals? :nerd_face:

Certainly not!

I wouldn’t ask you without having read that :wink:. I meant your explanation.

If we follow the adapted to FP monad definition in the Wikipedia article, what would be the bind operation for an Optional<T>? Note it would be (Optional<T>, (T) -> (Optional<R>)). This resembles optional chaining. But optional chaining isn’t part of Optional<T>.

I wouldn’t question the fact that Swift optionals resemble monads, but I don’t see how they are formally monads.

Try to write a Functor protocol with a map method, you’ll see that you can’t express that within Swift type system.

1 Like

As a starting point.

protocol Category { ... }

protocol Functor {

    associatedtype Category1: Category
    associatedtype Category2: Category
    
    func map(_ arg: Category1) -> Category2
}

// somewhere else:  T: Functor where T.Category1 == SomeCategory, T.Category2 == OtherCategory

This has a great potential to become a heated flame thread with little value added to the ecosystem. And I think the initial position of the Swift team makes a lot of sense already – let’s add more power to the language if there are legitimate use cases and we don’t degrate the language usability for regular users? If this is the case with higher-kinded types, let’s see those use cases and how they could be improved instead of arguing about FP in general.

2 Likes

Hi, FP can seems intimidating but it’s just a way to do things I’m not an expert in FP but if you want to stop your headache :D please consider reading this book Learn You a Haskell even if you only read a couple of chapters it will make you reconsider your everyday programming in any language you are using for the better. Have a great day.

I forgot to add this app Haskell for Mac it’s a playground for Haskell it’s great too.

4 Likes

This is not the definition of a functor. A functor maps objects, and arrows between them, from a category to another: in our case there’s only one category, Swift types, whose arrows are functions.

How would you make Optional (which is a functor) implement your protocol?

1 Like

Off the top of my head, a clear use case for HKTs is the ability to define a monad transformer, that helps a lot when nesting monads: I usually compensate with code generation, which is cumbersome and inefficient, but there’s no alternative. Another is to be able to represent a Profunctor, which is super useful when composing optics like Lens and Prism: without it, we need to write a lot of boilerplate.

But in general, it’s not up to us, the subset of developers writing in this thread, which is a subset of the Swift developers which write in the forums, which is a very small subset of the Swift developers worldwide, which is a subset of the developers who could adopt Swift as their primary language, to come up with use cases: there’s plenty in literature, and in the communities built around functional languages. The expressivity and sophistication of a type system come before any possibile use case, and it’s a purely theoretical endeavor, in which we discover mathematical properties, and find interesting ways to apply them to our problems. With something like polymorphism over type constructors we would unlock amazing possibilities to contribute to Swift in userland, without changes to the compiler or the standard library.

I’m not saying that Swift is unusable without HKTs, far from that, I’m simply stating that in a statically and strongly typed language with generics and protocols the usefulness of HTKs is absolutely clear, and has been demonstrated in many other languages and in many other contexts, there’s no doubt about it: I only fear that locking the ABI is going to be detrimental to the eventual inclusion of them to the language in the future.

2 Likes

Could you please formally explain why Optional<T> is a functor? An endofunctor, if we assume Swift types as the only category. In addition, the functor would be an object of the category since it’s a Swift type. I’m pretty sure it is clear to you that functions and protocols in Swift are types as well. A endofunctor has to associate each object to another object of the same category. How does this mapping look for Optional<T>?

There aren’t morphisms from arbitrary Swift types to other types, so similarly, why are Swift types a category to begin with?

That’s simply not true. Sophistication of a type system has downsides – implementation complexity, compilation speed, error message quality, learning curve, etc. For a good example, look at the comparison of Elm and Haskell. Elm is often ridiculed for its absence of type system features, yet at the same time sets the bar for good errror messages and welcoming learning curve. This is not something to be dismissed, especially since Swift strives to be a good language for regular users without CS background.

Which is why I think the core team is dead right when requiring convincing and concrete examples of real-world problems that would gain much better solutions after adding a new type system feature.

I agree that there are tradeoffs here, of course. What I’m saying is that a bunch of concrete examples (that you can already find online by the hundreds) is not what should convince the Swift core team to support a feature at the type system level: adding types, utility functions or new protocols to the standard library requires backing by relevant and numerous use cases, but the concept of HKT is something different. It would be like saying that adding generics to a language requires concrete examples: there are dozen and, for example, just showing the convenience in manipulating generic collections doesn’t do justice to parametric polymorphism in general.

5 Likes