Higher Kinded Types (Monads, Functors, etc.)

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

And even without the extension syntax, you're still able to express many use cases with constraints on members of the extension:

extension Array {
  func methodForOptionalElements<T>(...) where Element == Optional<T> { ... }
}
10 Likes

In 3 years of Swift development, that's the first time I've seen that syntax. I had no idea the where statement could be applied like that. Am I correct in thinking that limits the visibility of that function to Arrays with Optional elements, like an extension would?

3 Likes

Yep. You can further constrain T as well :) (Not the visibility though, right now you simply won't be able to use it because the compiler will emit an error like could not infer parameter type or could not convert...). Formally, however, it shouldn't be visible if the Array doesn't satisfy the condition.

Yeah, it should be equivalent for all intents and purposes to a constrained extension with extension-level type parameters, once those are supported. where clauses on nested declarations are allowed to impose constraints between their own type variables and their outer context's type variables. We still ought to allow the extension <T> Array where Element == Optional<T> syntax eventually, since it's something most developers expect to naturally work and it's more readable and less boilerplate than putting the same constraints on several commonly-constrained methods.

3 Likes

By the way, at present, should such a method be visible if the conditions aren't satisfied (code completion)? Just in case, right now they are always visible, together with methods like

extension Array where Element == Int {
   func foo(...) {...}
}
1 Like

Code completion shouldn't show it in either formulation, since it's statically obvious that the method can't be applied to the given self argument. I'd say that's a bug.

Filed it several weeks ago – SR-7046. Wasn't sure back then whether it's a bug or limitation.
I will update the issue with your example of a constrained method.

1 Like

I'm aware of that :smile: In fact, the generics manifesto is one of the things that I use when I recommend Swift to other people (interested in a language with a sophisticated type system): even if the generics system is still very incomplete, the manifesto shows that eventually we're getting there.

In times when I needed it, I've been using the solution proposed by @Joe_Groff

I think this way of emulation does not always work e.g. not as expressive as HKT.
Just from my humble and shallow understanding of FP and CT.

When I used your Swift HKT emulation idea in re-writing Haskell Parsec in Swift following ideas from Parsec Paper.
I encounter a difficulty to implement the following function

runParsecT :: Monad m => ParsecT s u m a -> State s u -> m (Consumed (m (Reply s u a)))

into

public func runParsecT <S, U, A, M:Monad>
  (_ p: Parser<S, U, A>, _ s: ParserState<S, U>, _ dummy: M) ->
  HKT_TypeParameter_Binder<M.HKTValueKeeper, ParserResult<HKT_TypeParameter_Binder<M.HKTValueKeeper, Reply<S, U, A>>>> {
    switch p.unParser(s) {
    case .consumed(let reply):
      switch reply {
      case let .ok(x, s_, e):
        let ok: Reply<S, U, A> = Reply<S, U, A>.ok(x, s_, e)
        
        // mok: HKT_TypeParameter_Binder<M.HKTValueKeeper, M.A>
        // M.A == Reply<S, U, A>
        let mok = M.return(ok as! M.A)
        
        // cok : ParserResult<HKT_TypeParameter_Binder<M.HKTValueKeeper, M.A>>
        let cok = ParserResult.consumed(mok)
        
        // mcok: HKT_TypeParameter_Binder<M.HKTValueKeeper, M.A>
        // M.A = ParserResult<HKT_TypeParameter_Binder<M.HKTValueKeeper, M.A>>
        let mcok = M.return(cok as! M.A)
        
        // Error: Cannot convert
        // HKT_TypeParameter_Binder<M.HKTValueKeeper, M.A>
        // into
        // HKT_TypeParameter_Binder<M.HKTValueKeeper, ParserResult<HKT_TypeParameter_Binder<M.HKTValueKeeper, Reply<S, U, A>>>>
        return mcok
      case let .error(e): fatalError("left to implement")
      }
    case .empty(let reply): fatalError("left to implement")
    }
}

As what I see, The M.A (the wrapped type in monad) cannot be two different type.
Because in Swift, every generic type should be deducible to a concrete type. Then when parsing this function, the type for M should be a concrete type, therefore M.HKTValueKeeper and M.A are concrete types as well.
So M.A cannot represent different types in the same context.

Is there something wrong in my reasoning. Please let me know.
By the way, actually, I love FP and CT, really looking forward that Swift can fully support FP and CT sooner or latter.

1 Like