How to capture hidden type variables in a variant in Swift?

Optparse-applicative takes an interesting approach to commandline parsing. A parser is data that captures the structure of applicative and monadic combinators so that you can inspect that structure and interpret it later. Modeling this in Swift is hard.

I want to be able to model something like this:

indirect enum Parser<T> {
   case NilP(v: T?)
   case AltP(p1: Parser<T>, p2: Parser<T>)
   case BindP<I>(p: Parser<I>, f: (I) -> Parser<T>)
   /* ... */
}

See Scala's optparse-applicative for reference

It seems like we'd need a protocol with an associated type to model this in Swift. And in order to return some arbitrary parser (think the result of a map call) we need type-erasure (AnyParser).

I've attempted that in this implementation (see BindP).

Going the protocol route, we can put all things that would be methods on the enum as methods in the protocol or a protocol extension (if it doesn't vary per variant). The map<B>(f: (A) -> B) -> B method does vary per parser case. This means it must exist on the protocol or be derivable by methods existing in the protocol in a protocol extension.

If it's declared in the protocol, then we need to store a closure for it in AnyParser, but we run into the problem of trying to store a generic map<B>:

struct AnyParser<T>: Parser {
    typealias A = T
    
    // TODO: How to do this?
    let _map<B>: ((T) -> B) -> AnyParser<B>
    
    init<P: Parser>(_ parser: P) where P.A == T {
        _map = parser.map
    }
    func map<B>(_ f: @escaping (A) -> B) -> AnyParser<B> {
        return _map(f)
    }
}

I realized that AnySequence exists and there is a map<B> function on Sequences. This seems to work because implementing sequence doesn't require you to implement map itself. You just provide an iterator. In a protocol extension, we can derive map<B> from the iterator.

I think something like that could work in this case, but I'm not sure what that method would be. Also, I'm open to other ideas. I feel that something like this should be possible in Swift. Somehow.

bkase/capture-hidden-type-variable-variant.md

bkase commented May 19, 2017

Uh oh!