Constraining Self to a protocol's associated type(s)

Question

Created Jun ’15

Replies 6

Boosts 0

Participants 3

Consider a protocol P with an associated type Q,

protocol P {
    typealias Q

    init(_ q: Q)
    func flatMap(f: Q -> Self) -> Self

    // Composeable from init and flatMap
    func map(f: Q -> Self.Q) -> Self
    // ... There are many others
}

and a conforming generic type C<T>, where T is constrained to Q

struct C<T> : P {
    typealias Q = T

    private let t: T
    init(_ q: T) {
        self.t = q
    }

    func flatMap<A>(f: Q -> C<A>) -> C<A> {
        return f(t)
    }

    // Compose from init and flatMap
    func map<A>(f: T -> A) -> C<A> {
        return flatMap { C<A>(f($0)) }
    }
}

This works

let c1: C<Int> = C(42) // t = 42
let c2: C<String> = c1.map { "\($0) is the answer" } // t = "42 is the answer"

With Swift 2.0, I'd expect to be able to use a protocol extension to share all combinators that can be composed from init and flatMap

extension P {
    func map(f: Q -> Self.Q) -> Self {
        return flatMap { Self(f($0)) }
    }
}

But, on removing the implementation of map in C—to expose the shared version in the extension—this is the result

let c1: C<Int> = C(42)
let c2: C<String> = c1.map { "\($0) is the answer" }
// error: cannot invoke 'map' with an argument list of type '((_) -> _)'

In the case of C, the compiler was able to connect Self.Q and Self with A and C<A> respectively, whereas in the extension the compiler seems to link Self.Q and Q to the conforming type itself.

Question 1. Is this the expected behaviour?

Question 2. Should there not be a way to restrict the various uses of Self through the associated type, e.g. Self<Q == A> or something similar—this syntax was suggested by someone else some time ago . Here's the way I would have liked to have approached this example.

protocol P {
    typealias Q
    init(_ q: Q)
    func flatMap<A>(f: Q -> Self<Q == A>) -> Self<Q == A>
    // Composeable from init and flatMap
    func map<A>(f: Q -> A) -> Self<Q == A>
}

extension P {
    func map<A>(f: Q -> A) -> Self<Q == A> {
        return flatMap { Self<Q == A>(f($0)) } // Inferrable?
    }
}

struct C<T> : P {
    typealias Q = T
    private let t: T

    init(_ q: T) {
        self.t = q
    }

    func flatMap<A>(f: Q -> C<A>) -> C<A> {
        return f(t)
    }
}

Although there has been some discussion in the past, I thought it should be raised again, given the protocol extension capability. Of course, such an approach may have other undesireable implications.

Looking forward to hearing opinions.

Boost

Answer 1

SteveMcQwark OP

Jun ’15

It seems to me that the only reason `C<T>` implements `P` to begin with is because you can substitute `T` for `A` in `C<T>.map<A>` and unify its signature with that of `P.map`. When you call `C<T>.map<A>` with `A != T`, you get a method that isn't part of the protocol. You can test this by trying to write a generic function that calls `P.map`:

func doMap<T: P, A>(t: T, f: T.Q -> A) {
    let c2 = t.map(f) // error
}

So, if you try to implement the method in a protocol extension, you'll only be implementing it for when `T == A`. This makes sense because `Q` and `Self.Q` are the same type—as are `Self` and `Self` for that matter. You can't really have `Self` at `T` and `Self` at `A`, because `Self` is `Self` at `T`. In fact, the protocol doesn't deal with parameterized `Self` types at all. `C<Int>` and `C<String>` are completely different types which implement `P` differently, one difference being that they have different `Q`s which happen to directly correspond to the type argument passed to `C`. `P` doesn't know this. For all it knows, the `Self` type might not even be a parameterized type. It could just be `Int`.

I do agree that being able to implement the pattern you're talking about would be useful. This is usually referred to a "higher-kinded types". To do this, you'd have to be able to write a protocol that you would implement on `C` instead of `C<T>`. Then, inside the protocol, you'd have `Self<Q>` and `Self<A>`. This is a complex design question, though.

0

Answer 2

rollandjb OP

Jun ’15

Thanks for your explanation. A couple of comments and questions:

It is intentional that C<T> connects T to P's associated type, so that C could acquire shared implementation of combinators.
Wouldn't C<Int> and C<String> actually share the implementation of P—certainly the code is the same—or are you referring to code generated by the compiler?
To what degree do you think a "higher kinded types" capability in Swift would be beneficial?
It seems to me the compiler is not being consistent in its treatment of Self and Q as described below.

Case 1: No extension defined. When the compiler accepts C<T>'s implementation of map

struct C<T> : P {
    typealias Q = T
    // ...

    func map<A>(f: T -> A) -> C<A> {
        return flatMap { C<A>(f($0)) }
    }
}

as a legal implementation of P.map

protocol P {
    typealias Q
    // ...
    func map(f: Q -> Self.Q) -> Self
}

it is matching Q to T, Self.Q to A, and Self to C<A>. This is even though one expects Self and Q to mean the same thing irrespective of their position in the declaration. If this is intentional, there should be a way of saying so explicitly in the declaration (e.g. Self<Q == A> or Self where Self.Q == A, or something better)

So, C<T>.map<A> with T != A actually is being treated as part of the protcol

let c1: C<Int> = C(42)
let c2: C<String> = c1.map { (i: Int) -> String in "\(i) is the Answer" } // This works

Case 2: Extension defined. In the case of the extension's implementation of map (and your doMap), all Self's refer to the same type as do all Q and Self.Q references. So here, when map is implemented by the the extension, or called generically via the protocol, only T==A matching conditions can be satisfied.

Should the compiler be accepting C<T>.map as a conforming implementation in case 1 in the first place? Is this intended behaviour?

0

Answer 3

nnnnnnnn OP

Jun ’15

Accepted Answer

In your original implementation, you've created C<T>.map as a broader method than required in the protocol. The protocol requires map(Q -> Q) -> Self, while C's map is declared as map<A>(Q -> A) -> C<A>. When A == Q, this is equivalent to what's required by the protocol, so the compiler is happy, even though C.map can also be used when A != Q.

When you try to move the implementation to the protocol, however, you're only dealing with what's defined there. Self in that context includes the generic's subtype, so it can only be replaced by the original type. That is, C<Int> can map to C<Int> but not C<String> or some other type D<Int>.

Note that when this works:

let c1: C<Int> = C(42) 
let c2: C<String> = c1.map { (i: Int) -> String in "\(i) is the Answer" } // This works

it isn't because of the protocol P—the only thing being used there is your implementation of map on C.

0

Answer 4

rollandjb OP

Jun ’15

With that clear explanation, I understand better what SteveMcQwark was saying.

Do you think that if the following was possible—with the corresponding changes in the protocol—it would be able to work as envisaged?

extension P {
    func map<A>(f: Q -> A) -> Self where Q == A {
        return flatMap { Self(f($0)) }
    }
}

0

Answer 5

nnnnnnnn OP

Jun ’15

Not exactly. The method signature would need to be:

extension P {
   func map<T: P>(f: Q -> T.Q) -> T {
       // ...
    }
}

That's saying that you can map to another P-conforming type T, using a closure that maps from the instance's generic subtype to any other generic subtype of T. But I don't think there's a way to constrain that T match whatever this is being called on—it can be any type that conforms to P.

0

Answer 6

rollandjb OP

Jun ’15

Well, given two sets of P-conforming types, C<T> and D<T> for any type T, I was trying to map from type C<T1> to C<T2> rather than from C<T1> to D<T2>, hence the use of Self.

0