Higher Kinded Types (Again)

Swift 5 happened and I want to discuss HKT again.

I road previous topic and want to tell about our experience. And I will try not to use FP terms at all.

We have some containers in our project.
It is:

  • Optional
  • Either
  • Promise
  • etc

We have map function and some operators to use these types as Functor (Mappable).
Optional already have map function, that works as fmap for Maybe in Haskell.

We want to append `<^> operator for correct function call order.

func <^><T, U>(_ transform: (T) -> U, _ arg: T?) -> U? {
    return arg.map(transform)
}

This code is correct, but we must declare this function for all of the containers: Optional, Array, Dictionary, Promise, Either and etc.

Now we want to append some sugar for Functor. We want to provide an operator to pass value instead of block. We must append this operator to all of the functors with the current type system.

func <^<T, U>(_ transform: T, _ arg: U?) -> T? {
    return arg.map { _ in transform }
}

We have 5 methods for this sugar instead of one.
At the finish, we have some map methods (for our own containers) and 2 operators for every container. We can't expand all of the Functors in one place. We can't guaranty that all of the functors implement all of the methods and operators.

We use Applicative pattern in our project and it awesome. We can do not use optional binding in most situation.

Applicative provide us use a function in container + value in the same container.
A simple implementation of the operator:

func <*><T, U>(_ transform: Optional<(T) -> U>,
                          arg: Optional<T>) -> Optional<U> {
    switch (transform, arg) {
    case (.some(let transform), .some(let arg)):
        return transform(arg)
    default:
        return nil
    }
}

It great pattern. Now we want to append function that takes transform function and 2 containers. Return result of function:

func liftA2<T, U, V>(_ transform: (T, U) -> V,
                                _ arg1: Optional<T>,
                                _ arg2: Optional<U>) -> Optional<V> {
    switch (arg1, arg2) {
    case (.some(let arg1), .some(let arg2)):
        return transform(arg1, arg2)
    default:
        return nil
    }
}

We can represent this function through Functor and Applicative pattern. It will have the same implementation for all of Applicative. And we write 5 versions of the function for all of the Applicative containers: Array, Optional, Promise and etc. And we have not to guarantee that developer provide this function for a container.

All of these problems can be resolved through HKT.

protocol Functor {
    associatedtype Element

    func map<T>(_ transform: (Element) -> T) -> Self<T>
}

Now we can expand all of the Functor with operators, additional method and other.

HKT is a good concept for reuse some code for containers.

5 Likes

I think the best way forward would be to have a proposal (and implementation) for generic associatedtypes, or for generalized existentials, as I mentioned in the previous HKT thread.

Generic associated types would enable this definition:

typealias Functor = Mappable
protocol Mappable {
    associatedtype Element
    associatedtype Mappend<T>: Mappable
      where Mappend.Mappend == Mappend,
            Mappend.Element == T

    func map<T>(_ transform: (Element) -> T) -> Mappend<T>
}
3 Likes

I very strongly support this, I've shown in the recent thread that HKT also allow expressing protocol Monad with a common flatMap signature. This can be reused across different types too: Array, Set, Optional, Result and all widely used future/promise types. Even though monadic DSL is more of a long-term thing, HKT would give us a strong foundation and common vocabulary to work with these patterns. Lack of it leads to duplicated code and confusion. Isn't the lack of HKT the reason for flatMap on Set returning an Array instead of Set?

2 Likes

No, the reason is that Set requires unique elements, and the mapping operation cannot guarantee it is one-to-one.

2 Likes

Fair enough, but even map is defined on Sequence as

func map<T>(_ transform: (Self.Element) throws -> T) rethrows -> [T]

which could make sense for Set, but definitely is a requirement too strong for an arbitrary Sequence.

A Set monad requires more than just HKT. It also requires something similar to ConstraintKinds in Haskell. If you search for the “constrained monad proble “ you’ll find some articles on this.

2 Likes

To the contrary – it is the very broad definition of what can be a Sequence that requires a definition like this. The limitation is not just with Set. You could not map a Range to Self either – the range requirements are even more restrictive than a set's.

A better example would be RangeReplaceableCollection. It redefines filter to return Self, because it does not change the Element type, and RRC has all the components needed to build filter (init() and append(_:)). But you cannot define a similar RRC version of map because you need higher-kinded types to return Self<T> for some mapping Element -> T

It is this potential for confusion over even the basic aspects that is one of the many reasons why my personal view is that HKTs probably do not belong in Swift, should be moved from the "Maybe" to the "Unlikely" section of the generics manifesto, and should maybe even be added to the Commonly Rejected list, at least for now.

(another being the operators proposed here, which are presented as motivating examples but IMO are hostile to even intermediate programmers not familiar with the concepts)

6 Likes

Not sure I follow why HKTs wouldn't belong in Swift when the abstraction should simplify a bunch of things in the standard library. I do think reframing them as something like "higher-order generics" might reset the concept and make it more palatable, though!

8 Likes

What if we approach this without the goal of fitting any of this 'on top' of the current machinery? If we had HKT and those interested in using them would need to build something up that was not guaranteed to 'simply' work with Collection and friends.

I'm still of the opinion that we should have the ability to express these ideas in the language. If access to these tools means dealing with some overhead, so be it. That overhead means that the 'intermediate' developers are less likely to stumble into it. Without HKT, there are useful and interesting concepts that we cannot adaquately express and it is a mistake, as I see it, to forsake those ideas because they are somewhat rarified.

5 Likes

Sorry, I'm not sure I'm following, isn't this one more reason to introduce HKT to be able to express map for RangeReplaceableCollection?

Could you please clarify what "for now" means here? If HKT is moved to "Unlikely" or "Commonly Rejected", what would be the condition for it to be moved back to "Maybe" in the future? What has to change in the future for you to reconsider it?

2 Likes

These operators not required for HKT.

I can't describe some useful types without HKT and must copy a lot of similar functions. And I haven't guaranteed that all of the functions will be written by other developers in a big team. Is it not enough for append more powerful type system?

1 Like