CODEWITHSUNDEEP
swiftgenerics
CompEng
CompEng

Reputation: 55

Function accepting a generic Collection and returning an array of indices

I'm trying to write a function that accepts a generic Collection and a single element, then returns the index or indices of this element as an array. However, I'm getting an error at the return statement.

enter image description here

func findAll<T: Collection, U: Equatable>(_ items: T, _ find: U) -> [U] where T.Iterator.Element == U {
    var found = [Int]()
    for (index, item) in items.enumerated() {
        if item == find {
        found.append(index)
        }
    }
    return found
}

Upvotes: 3

Views: 1451

Answers (2)

Rob Napier
Rob Napier

Reputation: 299355

Ken's answer is good, but Collection can have an Index other than Int. If you try to use the indexes you get back, you many not be able to subscript with them.

Instead of [Int], you want [Self.Index]. So instead of enumerated, you want the more general zip:

extension Collection where Self.Element: Equatable {
    func indicesOfElements(equalTo element: Self.Element) -> [Self.Index] {
        return zip(self.indices, self)    // Zip together the index and element
            .filter { $0.1 == element }   // Find the ones that match
            .map { $0.0 }                 // Return the elements
    }
}

[1,2,3,4,1].indicesOfElements(equalTo: 1) // => [0,4]

That said, a simpler approach would be:

extension Collection where Self.Element: Equatable {
    func indicesOfElements(equalTo element: Self.Element) -> [Self.Index] {
        return indices.filter { self[$0] == element }
    }
}

To see the problem w/ subscripting, consider this:

let s = "abcabc"
let i = s.indicesOfElements(equalTo: "a").first!
s[i] // "a"

let j = findAll(s, "a").first!
s[j] // error: 'subscript' is unavailable: cannot subscript String with an Int, see the documentation comment for discussion

While a protocol extension is the preferred way to do this in Swift, this is directly convertible to the following generic function syntax:

func indicesOfElements<C: Collection>(in collection: C, equalTo element: C.Element) -> [C.Index]
    where C.Element: Equatable {
        return collection.indices.filter { collection[$0] == element }
}

The following style is also equivalent, and has a slightly shallower learning curve (no need for filter.

func simplerIndicesOfElements<C: Collection>(in collection: C, equalTo element: C.Element) -> [C.Index]
    where C.Element: Equatable {

        var results: [C.Index] = []

        for index in collection.indices {
            if collection[index] == element {
                results.append(index)
            }
        }

        return results
}

I believe even fairly new Swift developers should learn to read simple filter and map expressions (though these should aways be kept simple, even by experts!) But there is absolutely nothing wrong with learning simple for iteration first.

If you're just getting started, note the naming style here as well. Your initial example included two unnamed parameters. In many (most) cases this is poor Swift. In Swift we generally try to name our parameters such that they read fairly naturally in English. In findAll(xs, x) it's unclear what the parameters are or what the return value will be in. In indicesOfElements(in: xs, equalTo: x), all the information is available at the call site.

In Swift 3, this takes a lot more syntax than you probably expect:

func indicesOfElements<C: Collection>(in collection: C, equalTo element: C.Iterator.Element) -> [C.Index]
    where C.Iterator.Element: Equatable, C.Indices.Iterator.Element == C.Index {
    // ... Same body ...
}

In Swift 3, associated types can't have additional constraints put on them. This seems a small thing, but it's huge. It means that there's no way to say Collection.Indices actually contains Collection.Index. And there's no way to create a Collection.Element (the type returned by subscripting the collection) that is promised to be the same as Collection.Iterator.Element (the type returned by iterating over the collection). This leads to a lot of C.Iterator... and where clauses that seem obvious like C.Indices.Iterator.Element == C.Index.

If you're near the start of your Swift journey, I'd probably skip over the generics entirely, and write this in terms of [Int]. A very common mistake by Swift programmers (new and "old") is to jump to generic programming before they have any need of it. But if you're at the stage where you're tackling generics, this is how you often have to write them in Swift 3. (Swift 4 is a dramatic improvement for generic programming.)

Upvotes: 4

Ken Darragh
Ken Darragh

Reputation: 59

Since you would like to return the indices of the found elements, you should return an array of Ints instead of [U]. Here's the updated code:

func findAll<T: Collection, U: Equatable>(_ items: T, _ find: U) 
  -> [Int] where T.Iterator.Element == U {

    var found = [Int]()
    for (index, item) in items.enumerated() { 
        if item == find {
            found.append(index)
        }
    }
    return found
}

And here's a test case: 

let numbers = [1,0,1,0,0,1,1]
let indicesOfOnes = findAll(numbers, 1)
print(indicesOfOnes)

Which will print:

[0, 2, 5, 6]

Upvotes: 1

Related Questions