How do I use opaque return types with lazy sequences?

Using Swift
, ,
1

So here's what I'd intuitively write:

func process(_ array: [Int]) -> some LazySequence<Int> {
    array.lazy.filter { 0 != $0 }
}

Unfortunately, LazySequence is a struct, not a protocol. (it also requires its primary associated type be the type of the base sequence, [Int] in this case, not the Element, which is its own can of annoyance but irrelevant here)

There does exist LazySequenceProtocol, but it has no primary associated type. So no bueno:

func process(_ array: [Int]) -> some LazySequenceProtocol<Int> {
    array.lazy.filter { 0 != $0 }
}

:stop_sign: Protocol 'LazySequenceProtocol' does not have primary associated types that can be constrained

(also, it complains that 'some' types are only permitted in properties, subscripts, and functions which is confusingly irrelevant since some is clearly being used in a legal place)

If I drop the primary associated type:

func process(_ array: [Int]) -> some LazySequenceProtocol {
    array.lazy.filter { 0 != $0 }
}

…then it does technically work (compile) but of course the caller(s) of this are hassled by (some LazySequenceProtocol).Element being undefined, requiring force-casting at the least.

Even if you forget about making the return type in any way opaque - assuming that's even a viable option in any given case - it's exceptionally ugly and tedious to do so if your lazy pipeline is non-trivial, since you end up with horrific function signatures like:

func process(_ array: [Int])
 -> LazyFilterSequence<
        LazyMapSequence<
            LazyFilterSequence<
                LazyMapSequence<
                    LazyFilterSequence<
                        LazySequence<
                            Array<Int>
                        >,
                        Int
                    >
                >,
                Int
            >
        >
    > {
    …
}
2

You can refine LazySequenceProtocol to have a primary associated type and extend all known types conforming to it to your refined protocol.

public protocol TypedLazySequenceProtocol<Element>: LazySequenceProtocol {}
extension LazySequence: TypedLazySequenceProtocol {}
extension LazyMapSequence: TypedLazySequenceProtocol {}
extension LazyPrefixWhileSequence: TypedLazySequenceProtocol {}
extension LazyDropWhileSequence: TypedLazySequenceProtocol {}
extension LazyFilterSequence: TypedLazySequenceProtocol { }
extension Slice: TypedLazySequenceProtocol where Base: LazySequenceProtocol { }
extension ReversedCollection: TypedLazySequenceProtocol where Base: LazySequenceProtocol { }

func process(_ array: [Int]) -> some TypedLazySequenceProtocol<Int> {
  array.lazy.filter { 0 != $0 }
}
1 Like
3

That's a somewhat clever workaround.

Alas not scalable or broadly applicable, though (not just from a labour perspective, but because 3rd party modules can define their own lazy sequence types, which (a) one doesn't know about and (b) they can't conform to this protocol because they don't own it).

4

How’s some Sequence<Int> & LazySequenceProtocol? Not exactly pretty but handles what you need. (Untested, though—maybe this isn’t implemented.)

7 Likes
5

Ah, that does work! A tad verbose, but at least in initial testing I don't see any apparent side-effects or limitations…

6

Nice! And on top of that there could be a typealias

typealias TypedLazySequenceProtocol<Element> = Sequence<Element> & LazySequenceProtocol

func process(_ array: [Int]) -> some TypedLazySequenceProtocol<Int> {
  array.lazy.filter { 0 != $0 }
}
2 Likes
7

could we add a primary associated type to it? cc @lorentey

1 Like
8

I hope so. @jrose's workaround is pretty good, but it's (IMO) unintuitive - evidently I had to bother all you nice folks to figure it out - and of course not as concise as it could be.

I'm also curious, tangentially, what this LazySequence struct is and why it's camping out on the name that much more obviously should have been given to the protocol? I assume it's practically impossible to change that now, but I'm still curious how it ended up that way.

9

This is point (1) in the Alternatives Considered section of SE-0358.

(1) It is tempting to declare Element as the primary associated type for LazySequenceProtocol and LazyCollectionProtocol, for consistency with other protocols in the collection hierarchy. However, in actual use, Elements seems just as useful (if not more) to be easily constrained. We left the matter of selecting one of these as primary unresolved for now; as we get more experience with the lightweight constraint syntax, we may revisit these protocols.

IIUC, @wadetregaskis is arguing that choosing Element (not Elements) would be the right choice.

One question I have is why not just have the function return a Sequence?

func process(_ array: [Int]) -> some Sequence<Int> {
    array.lazy.filter { 0 != $0 }
}

The answer to this may illuminate whether it'd be worth revisiting this decision.

2 Likes
10

There's two potential reasons, although I'm not yet certain either are strong:

  1. I don't trust type inference to use an appropriate lazy sequence type if I just return some Sequence<Int>.

    As context for how I ran into this, I'm trying to explore and better document the pitfalls of lazy Collections and Sequences, one of the biggest of which is type inference grabbing at eager versions of methods by mistake.

    Possibly this specific situation - some Sequence<Int> - wouldn't be afflicted by that, but I suspect some Collection<Int> is at least.

  2. There may be situations where it's semantically important, if not tangibly important for performance (both compile times and program runtime), to ensure lazy sequences are used.

    This applies similarly to the question "why would you ever require a LazySequenceProtocol argument instead of just accepting any Sequence? I don't have a specific example of this yet, though.

1 Like
11

but then .lazy wouldn’t propogate, you’d have to repeat it.

1 Like
12

There is that too, although I consider it pretty minor. .lazy on something that's already lazy should in principle just return self and be trivially optimised away by the compiler. Though I haven't confirmed that. Assuming it's the case, though, then it's just a minor bit of boilerplate in your code.

…although it may relate back to my prior point about enforcing certain semantics, such as preventing callers of my example function from naively using eager methods. I'm still exploring that avenue too, but I'm pretty sure it's full of dragons - it lets callers make the same mistakes the compiler already does with e.g. using Collection.map instead of Sequence.map and causing the whole lazy pipeline to be evaluated twice (e.g.).

13

Oh, do you mean that array.lazy.filter {...} may somehow end up falling into the default Sequence algorithm, and the function returning an Array instead of a LazyFilterSequence?

That would be quite surprising; if it actually happens, then I think that would count as a language defect.

I expect array.lazy.filter to invoke the lazy filter member, as it is defined on a more specific protocol.

The only way to have it resolve to Array is to explicitly narrow it to that return type:

let a = [1, 2, 3]
let b: Array = a.lazy.filter { $0 / 2 == 0 }
// b is now [2]

This cannot happen in the process function's case. (Each function must have a single, well-defined return type. The type returned must not (cannot) depend on the caller's expectations.)

1 Like
14

This isn't the only case where primary associated type isn't enough, because what's "primary" may depend on the use site. some P means both: opaque return type determined by the body, and constraint : P for the type. But : P isn't the only constraint one might want to apply. It'd be nice to be able to setup any set of constraints.

15

Ah, but given (as @jrose so nicely points out) that one can return some Sequence<Int> & LazySequenceProtocol, is there anything not expressible unless LazySequenceProtocol itself gains a primary associated type of Element?

Since the primary associated type of Sequence is unambiguous, it seems to me that wide adoption of this compositional idiom is actually really sensible.

16

With @jrose's pattern constrain on Element is expressible because of lucky unambiguous primary Element of Sequence. Constraint on Elements isn't expressible right now.

func f() -> some LazySequenceProtocol 
  where __OpaqueReturnType.Elements == [Int]

Also, suppose Sequence doesn't have a primary associated type. Then LazySequenceProtocol should refine one more synthetic protocol:

protocol LazySequenceProtocol: Sequence, WhereElement {
  associatedtype Elements: Sequence
  var elements: Elements { get }
}
protocol WhereElement<Element> {
  associatedtype Element
}
func f() -> some LazySequenceProtocol & WhereElement<Int>

Any protocol with more that 1 associated type may struggle of this.

17

It might be. It can be read as "I need a Sequence of Ints, and I want it to be lazy". Composition; could make sense.

It definitely seems to work, which is of course a major point in its favour.

I'm still unsure about how intuitive that pattern is expected to be, though. I've long been aware that one can conjoin protocol requirements like that, I just have rarely (if ever…?) done so in real-world code.

Are there any other examples that come to mind where this sort of thing is (in some sense) common?

This is mostly for my curiosity, I suppose. I'm more concerned by the naming of these components than their use in composition. e.g. LazySequence vs LazySequenceProtocol, or why it's not simply Lazy if it's essentially an attribute marker protocol that's meant to be composed with a 'concrete' protocol.

18

That can easily happen in cases where the filter is some closure provided as an argument, and you forget to annotate the argument with @escaping

2 Likes