Higher Kinded Types (Monads, Functors, etc.)

Monads can be used to model effectful computations. Abstracting over the monad used to interpret the computation can be extremely useful. The most obvious and immediate example is to substitute a mock interpreter used by tests.

This is a really deep topic. If you're interested in learning more I recommend looking at what folks in the Scala and Kotlin communities are doing. These communities have a more fully developed ecosystem for working with these abstractions than we do in the Swift community. A good place to start might be this video: Functional approach to Android architecture using Kotlin - Jorge Castillo - YouTube.

6 Likes

So what is effectful computations? Even google only list some obscure hits. Any short and easy explanation that we non math majors have a chance to understand what the feature is about?

A nice simple example is modeling the side effects of an interactive console application. The computation can write to the console and request input from the user. There is a brief overview of the concrete benefits of this approach in the talk Beyond Free Monads given by John de Goes at a Scala conference last year.

If you're really interested in learning about these techniques I suggest you take a look at this and the prior You Tube link I shared. It will take more than a few minutes but maybe you will find it worth the time you invest.

Well at least I have a splitting headache again but still don't see why not simply use a normal io function/method. What I guess from it is that effectful computations means "has sideeffects". See that was an easy explanation that many developers will understand. Why make it more complicated by packing it into a new name?

It's more general than that, but side effects are a useful subset that is pretty straightforward to think about.

Here's an example related to something that I use pretty frequently in my code.

Assume you have an Array<String> that you want to transform into an Array<Int>; you have a function transform: (String) -> Result<SomeError,Int> because you need to be precise about the cases where a String cannot be transformed into an Int.

If you map your array you end up with an Array<Result<SomeError,Int>> but you would really like this to be the other way around, that is, Result<SomeError,Array<Int>>, so that the transformation results in a single Result with an eventual error representing the first error found, or more informatively all the errors produced within the original array.

It turns out that you can do this generically because Result is an applicative functor, that is, it provides a way to construct a result with a single value, and a way to apply a function to a result when the function is itself contained into a result. Thus, the only thing that you require from result is a .pure static method, and an "apply" operator <*>.

Now, suppose you have a Future<A> type: a future is an applicative functor too (actually, in more than one way), so if your function was a transform: (String) -> Future<Int> you could use the exact same method to get a Future<Array<Int>>.

That's because that method (let's call it traverse) requires a function of type (Element) -> T where T is an applicative functor, but this can't be represented in Swift, so you need to write a lot of specialized functions with the same shape and only different names for the concrete types.

You can find some more examples in a library I wrote that adds a bunch of functional constructs to Swift, but in a Swifty way (in the sense that favors methods over free functions and operators): can I link that here?

6 Likes

So by ‘effectful’ here, you mean computations with IO. You model these so everything is performed lazily, with a type modelling each kind of operation. Things end up naturally composing lazily, similar to the Collection.lazy view's methods.

What I (hopefully) understood from the video, is that these concepts being protocols allows extensions to flatten the related API, removing the need to unwrap each level when they're nested. A concrete example:

extension Optional where Wrapped: Optional {
    func map<B>(_ transform: (Wrapped) -> B) -> Optional<B> {
        switch self {
        case .some(let wrapped): return wrapped.map(transform)
        case .none: return .none
        }
    }
}

When this kind of thing is automatic, you stop having to worry about the huge amounts of generic nesting you get with functional programming, and can unwrap however many levels in one go. Is that the gist of it?

I would say that "side effect" means "modifying state outside a local scope", like for example mutating an object passed as input, or a global variable. "Effectful" in general means this but also more, like reading from a global mutable state, or passing some state around from context to context. Monads are a tool to model these kinds of things, in a way that turns impure functions into pure ones, and allows better and easier reasoning about code (assuming that one knows what those monads mean, of course).

A very simple example is an if statement over a "nullable" value: if I check for the value's existence, and enter a branch of my if, there's literally no other way for me to do something actually useful in my program than mutating some external variable in the outer scope. That's why Optional exist: I can model the idea that a value exists or not, and keep working like it did, maintaining purity in functions.

It's "one" gist :smiley:

Nested functors are better handled with monad transformers, something that could be expressed if we could write a Monad protocol.

No, IO as I said above computational effects are more general than IO. For example, the list monad models non-deterministic computation: 12. The List Monad - School of Haskell | School of Haskell. This does not involve any IO at all.

Which video and what specific section are you asking about? The Optional example you posted is the Optional implementation of the map (or often called fmap) requirement of a hypothetical Functor protocol.

1 Like

The good news is that we can! (in a vastly less than ideal fashion)

Here are a couple of links if you're interested in discovering how to emulate and work with HKT in Swift today:

1 Like

I don't think I'll fully grasp the amount of application until I try this out. Thanks for the explanations.

Around the part where typealiases got involved.

And that's the kind of thing which could be made a protocol extension, along with a vast amount of other functions, to my understanding.

I'm aware of this kind of emulation, and I consider it cumbersome and ugly: to me it's more of a proof-of-concept than something really usable in the long term, and for my applications I preferred some amount of code generation.

The Kotlin community has gotten pretty far with this kind of emulation (http://arrow-kt.io), but I agree it's far from ideal. Kotlin also supports coroutines which allowed them to implement "monad comprehension" syntax. It will be a while before we're able to do something like that in Swift.

1 Like

I'd like to reiterate what Elviro has said here with a few more examples, cause it's really interesting!

There are often times that we have nested generic types, and we wanna "flip" around their order of nesting. For example:

  • [A?] -> [A]?: You may have an array of optionals that you want to map to an array of non-optionals, but only if there are no nil values inside.

  • Generalizing the above, [Result<A, E>] -> Result<[A], E>: You want to convert an array of results into a result of all the values, but only if all the results were successful.

  • Result<A?, E> -> Result<A, E>?: You want to convert an optional inside a result to a non-optional by making the whole result optional.

  • [Future<A>] -> Future<[A]>: You have an array of futures that you want to turn into a future of an array but running all the async operations and collecting their values.

  • (A?, B) -> (A, B)?: You want to convert an optional value in a tuple to a non-optional by making the whole tuple optional.

And this is only the beginning! If you squint you will see that in all of these cases we are simply flipping the order of the nesting of generic types: F<G<A>> -> G<F<A>>.

Now, we can very easily implement all of these functions, and it can be a fun exercise. However, higher-kinded types allow you to abstract over this pattern so that you just make Optional, Array, Result, Future, etc. conform to a particular protocol and then you get all the above properties for free. And even better, any 3rd party types that conform to that protocol also get to participate in this container flipping fun without you having to know anything about them. So that amazing Baz<A> type that you have been working hard on in the amazing BazKit framework gets to do transformations like:

Optional<Baz<A>>  -> Baz<Optional<A>>
Result<Baz<A>, E> -> Baz<Result<A, E>>
Array<Baz<A>>     -> Baz<Array<A>>
Future<Baz<A>>    -> Baz<Future<A>>

for free, without knowing anything about those other types. And that is pretty powerful!

16 Likes

They did an amazing work, and they are working hard to come up with a complete, fully featured proposal to add HKTs to Kotlin, because they too realize that the emulation solution can only go that far.

I closely follow Kotlin's development, and there's plenty of power there in areas where Swift is sadly lacking: one of the things I miss the most is the ability to write generic extensions (extension functions in Kotlin), for example in Swift we literally cannot write something like this:

extension Array where Element == Optional {}

Because it would require a generic parameter somewhere. A perfect solution would be:

extension <A,B> Array<A> where A == Optional<B> {}

This still makes free functions a lot more powerful in Swift than extensions. But let's not derail the thread: I think we made a case for HKTs in Swift. This is not some fringe, obscure idea: is something that's basically taken for granted in highly successful, highly powerful languages, and would make Swift definitely more expressive, powerful and future-proof.

7 Likes

I agree and am aware of the proposal for adding HKT to Kotlin. Please don't take anything I said as an argument against adding HKT to Swift! :) Unfortunately it sounds like it will be at least a couple years before they make it to the top of the priority list for Swift. IMO we should take the language as it exists as far as we can, continuing to make the case stronger in the meantime.

1 Like

I definitely agree. I also think that there are more "urgent" things related to the generics system, like my example with generic extensions, that are straight-out missing from the Swift type system but should really have been there from the beginning (like conditional conformances, that we're finally getting in 4.2). If there's no problem related to the ABI, I think we'll be fine for another couple of years :smiley:

Agree. Another missing generics feature that I run into pretty frequently is the lack of generalized supertype constraints.

2 Likes

FYI, this feature is on Swift's generics manifesto as parameterized extensions.

Doug