Recursively slice an array

Using Swift
1

I noticed strange behavior in type System. Look at next functions

    func drop() {
        let a = [1, 2, 3]
        let b = a.dropLast() // Array<Int>.SubSequence
        handle(a: b)
    }
    func handle(a: [Int]) {
    }

It does not compile, because b is type of ArraySlice<Element> while the function handle(a: [Int]) wants the type [Int].
BUT If we are slicing an array within handle(a: [Int]) the code compiles and works

    func run() {
        handle(a: [1, 2, 3])
    }
    func handle(a: [Int]) {
        if a.isEmpty { return }
        handle(a: a.dropLast())
        print(a)
    }
/// [1]
/// [1, 2]
/// [1, 2, 3]

Is it hack? Or I have a mistake somewhere?

2 Likes
2

UPD, I understand, it is static dispatcher magic, and invokes an extension on Sequence protocol. But what is the most memory efficient way to recursively slice an array?

3

Would you mind elaborating a bit on why the program compiles? I see both Sequence and Array have dropLast(). The former returns [Self.Element], the latter returns ArraySlice<Element>. Since the program compiles, it seems that the compiler somehow determines that it should use Sequence's method. Why?

As far as I can tell, there is no existential type involved in the program, how does the static dispatch come into play?

4

Since handle(a:) wants an Array, the compiler looks for a way to make a.dropLast() return an Array.

It happens that Array.dropLast(_:) has no default argument, and Collection.dropLast(_:) does not return an Array, so they are not suitable options. On the other hand, Sequence.dropLast(_:) is a good fit.

You just witnessed method overloading. Another example:

let a = [1, 2, 3]

let b = a.dropLast()                    // Collection.dropLast
let c = a.dropLast() as ArraySlice<Int> // Collection.dropLast
let d = a.dropLast() as [Int]           // Sequence.dropLast
let e: [Int] = a.dropLast()             // Sequence.dropLast

I can't find in the Swift Book a documentation of what overloading is, and what are the static resolution rules. In a nutshell, the compiler looks for a suitable implementation in the available overloads, with a preference for the most precise one when there is an ambiguity.

It is this preference which explains why a naked a.dropLast() is the precise Collection.dropLast. This preference disfavors the more general Sequence.dropLast. And it avoids an "Ambiguous use of dropLast()" compiler error.

EDIT: Fixed explanation by replacing Array.dropLast(_:) with Collection.dropLast(_:) (only the Collection overload has a default argument).

3 Likes
5

If you only want that it works for Array<Int> the easiest solution is to start with an ArraySlice<Int>. You can get an ArraySlice<Int> of the full array by using the [...] subscript which is a rather hidden feature of Swift:

func drop() {
    let array = [1, 2, 3] // Array<Int>
    let slice = array.dropLast() // ArraySlice<Int>
    handle(a: array[...]) // ArraySlice<Int> of the full aray
    handle(a: slice)
}

func handle(a: ArraySlice<Int>) {}

Your recursive algorithm can slice an ArraySlice again and again and again and will always get back an ArraySlice. This is actually the case for all types conforming to the Collection protocol: https://github.com/apple/swift/blob/17f1cf92973d2c1b3d5fe6b70f4a33771a303e3a/stdlib/public/core/Collection.swift#L390-L398

4 Likes
6

Thanks for the explanation. I did a bit more search and find Array.dropLast(_:) seems to inherit from BidirectionalCollection. The hierarchy is as below:

Sequence
-> Collection
   -> BidirectionalCollection
      -> RandomAccessCollection
          -> Array

I usually think overloading applies to methods on the same level. So the behavior seems to indicate that Swift doesn't give method in child protocol higher priority (I know there were a lot of discussion in the forum about behaviors with regarding to protocol methods, but I didn't pay much attention to them in the past. I just avoided the pitfalls.).

If Array defines its own dropLast(_:), I guess the behavior might be different and that method would always be used. Just my guess.

7

You have a wonderful tool for moving one level up, and perform educated guesses instead: test your hypothesis with Swift playgrounds.

1 Like