Error: some' cannot appear in parameter position in result type '(some Sequence) -> some Sequence'

Hi, community.

I am defining a generic map function:

func map<A, B>(_ f: @escaping (A) -> B) -> (some Sequence<A>) -> some Sequence<B> {
    return { xs in xs.map(f) }
}

and I get the error:

some' cannot appear in parameter position in result type '(some Sequence) -> some Sequence'

How can I solve this ?

An opaque parameter (a some parameter) is syntactic sugar for a generic parameter. For example, this function with an opaque parameter:

func map<A, B>(xs: some Sequence<A>, _ f: (A) -> B) -> some Sequence<B> {
    return xs.map(f)
}

is syntactic sugar for this function with an additional generic parameter:

func map<A, B, S>(xs: S, _ f: (A) -> B) -> some Sequence<B>
where S: Sequence, S.Element == A
{
    return xs.map(f)
}

Now let's look at your function:

If we try to de-sugar the opaque parameter, we end up with something like this:

func map<A, B>(_ f: @escaping (A) -> B)
    -> (<S> (S) -> some Sequence<B> where S: Sequence, S.Element == A)
{
    return { xs in xs.map(f) }
}

Which is to say, your map function wants to return a generic function.

Unfortunately, in Swift, generic functions are not “first-class”: you cannot treat a generic function as a value. For example, you can't do this:

func identity<A>(_ a: A) -> A { a }

let id = identity // error: Generic parameter 'A' could not be inferred

You can only turn a generic function into a value if you provide all the generic parameters, thus producing a non-generic function:

func identity<A>(_ a: A) -> A { a }

let id_Int = identity as (Int) -> _

Since you can't treat a generic function as a value, you can't return a generic function.

As for how you can solve your problem, it depends. Why are you trying to return a generic function?

One solution, which may or may not be applicable to your problem, is to return a value of some type that has a generic function. For example:

struct Mapper<A, B> {
    let f: (A) -> B

    func callAsFunction(xs: some Sequence<A>) -> some Sequence<B> {
        return xs.map(f)
    }
}

func map<A, B>(_ f: @escaping (A) -> B) -> Mapper<A, B> { .init(f: f) }
2 Likes

Thank you so much, Rob !

However, I am able to call id with any parameter type. Could you give me a little bit more insight into the problem ? Why can I use the function, but do not assign it ?

I often take advantage of partial applications, so I would like to have a generic map function.

The following also doesn't work:

func map1<S: Sequence, T: Sequence>(_ f: @escaping (S.Element) -> T.Element) -> (S) -> T {
    return { xs in xs.map(f) }
}

But this one does:

func map1<A, B>(_ f: @escaping (A) -> B) -> (any Sequence<A>) -> any Sequence<B> {
    return { xs in xs.map(f) }
}

Do you know why ?

You can call identity (as I defined it) with any parameter type. You cannot call id at all (as I defined it) because Swift rejects its definition.

You can call identity because when you pass a value parameter, Swift uses the value parameter's type to infer the generic parameter. For example:

let i = identity(1)

Above, Swift infers type Int for the literal 1, and so it infers type Int for the generic parameter A.

Another example:

let a = identity(assert)

The global assert function has type (@autoclosure () -> Bool, @autoclosure () -> String, StaticString, UInt) -> (), so Swift infers that type for the generic parameter A.

That doesn't compile because xs.map is the map function defined as an extension to protocol Sequence, which returns Array<T.Element>. But T might not be Array<T.Element>; it might be some other type that implements Sequence.

We can fix that problem by constraining T to RangeReplaceableCollection, so that we can convert Array<T.Element> to it:

func map1<S: Sequence, T: RangeReplaceableCollection>(_ f: @escaping (S.Element) -> T.Element) -> (S) -> T
                          ^^^^^^^^^^^^^^^^^^^^^^^^^^
{
    return { xs in T(xs.map(f)) }
                   ^^         ^
}

Once we fix that, we can try to use it:

let transform: (Int) -> String = { String(describing: $0) }
let m = map1(transform)
// error: Generic parameter 'S' could not be inferred
// error: Generic parameter 'T' could not be inferred

We run into trouble, because, again, generic functions are not first-class. The map1 function cannot return a generic function; it must return a function with no generic parameters. But there is nothing in the call map1(transform) that lets Swift infer types S and T.

We can let it infer S by calling the returned function immediately:

let m = map1(transform)([2, 3, 5])

This lets Swift infer type Array<Int> for generic parameter S, but Swift still doesn't know what to substitute for generic parameter T.

We can let it also infer T by specifying the type of m:

let m: Array = map1(transform)([2, 3, 5])

This is sufficient to compile, because now Swift can infer type Array<String> for generic parameter T.

We can also specify the specific type returned by map1, and that gives a non-generic function we can store in a variable:

let m: ([Int]) -> [String] = map1(transform)

// or this way:
let m = map1(transform) as ([Int]) -> [String]
2 Likes

This works because any Sequence<A> is not generic. It is not like some Sequence<A>, hiding a generic parameter.

The compiler infers generic parameters A and B from the type of f at the call site. So the compiler has concrete types to substitute for A and B in the returned function.

The type any Sequence<A>, given a real type to substitute for A, is a concrete, non-generic type, called the “existential” of Sequence with the constraint that the Element type of the Sequence is A. It is a “wrapper” or “box” that can hold any value whose type conforms to Sequence with Element type A.

2 Likes

Oh, wow. Rob, I deeply appreciate such a through and comprehensive explanation !

I do not understand this. I am able to use it with any parameter. How is that possible ? Perhaps, my use of generic is not the appropriate for this case.

1 Like

Sorry for being unclear.

Consider this signature:

func map_any<A, B>(_ f: @escaping (A) -> B)
  -> (any Sequence<A>)
  -> any Sequence<B>

This map_any isn't really a function. It is a function constructor with two generic (type) parameters: A and B. To use it to construct a function, you must ‘call’ map_any with two type arguments: one for A and one for B.

Swift doesn't have a syntax for directly ‘calling’ the function constructor with just type arguments, but you can let it infer the type arguments by specifying the type you want the ‘call’ to the function constructor to return. For example, you can ‘call’ it like this:

let map_any_Int_String: (@escaping (_) -> _)
  -> (any Sequence<Int>)
  -> any Sequence<String>
  = map_any

Above, Swift deduces that you want to pass Int for the A type parameter, and String for the B type parameter.

You can also let Swift infer some type arguments by passing a value for the f parameter. For example:

let map_any_Int_String = map_any {
    (i: Int) -> String in "\(i)"
}

Above, the function literal { (i: Int) -> String in "\(i)" } is fully typed and so Swift can use it to infer A = Int and B = String.

So, in my prior post, when I said any Sequence<A> is not generic, what I meant was that, when you ‘call’ map_any to construct a function, you get back a function that has no generic type parameters left; Swift ‘filled in’ all the type parameters in order to construct the returned function.

Now consider this signature:

func map_some<A, B>(_ f: @escaping (A) -> B)
  -> (some Sequence<A>)
  -> any Sequence<B>

This use of some is syntactic sugar for an anonymous type parameter. It could reasonably be desugared in one of two ways. One way to desugar it is like this:

func map_some<A, B, S>(_ f: @escaping (A) -> B)
  -> (S)
  -> any Sequence<B>
where S: Sequence, S.Element == A

This is a valid Swift type signature. Again, this is a function constructor, not a function. To make a function, you have to ‘call’ it with three type arguments: one for A, one for B, and one for S. Again, you can do that by specifying the type you want the ‘call’ to return:

let map_some_Int_String: (@escaping (_) -> _)
  -> (Array<Int>)
  -> any Sequence<String>
  = map_some

You can also ‘call’ it if you pass a value for f and then immediately pass a value for the anonymous parameter of type S:

let strings: any Sequence<String> = map_some { "\($0)" }([2, 3, 5])

Above, Swift infers B = String from the declared type of strings, infers A = Int from the literals 2, 3, and 5, and infers S = Array<Int> from the literal [2, 3, 5].

What you cannot do is ‘partially apply’ map_some by providing just types for the A and B parameters, while leaving S unspecified. You cannot do this:

let map_some_Int_String: (@escaping (Int) -> String)
  -> (_)
  -> any Sequence<String>
  = map_some

and you cannot do this:

let stringify: (some Sequence<Int>)
  -> any Sequence<String>
  = map_some { "\($0)" }

because Swift cannot infer a type for S in either of those cases. This goes back to what I said in my first post: in Swift, generic functions (which are really function constructors) are not first-class. A function constructor can only be ‘called’ if Swift can infer types to pass for all of the type parameters. You cannot store a function constructor in a variable or pass one as an argument or return one from a function.

2 Likes

Thank you for the clarification and the super helpful explanation.

What's a function constructor ? Could you tell me where I can find more info ?

Why did you use a colon, and a double equals sign in the same line ? Do they have different uses ?

I do not get this, yet. When you say: "you get back a function that has no generic type parameters left; Swift ‘filled in’ all the type parameters". Is that the difference between some and any ? Using any the generic parameters are filled in ? But, I didn't specific them either. The same happens with some, I think.