Open michaeleisel opened 3 years ago
That example could be written quite easily with filter(_:)
without the need for a separate without(_:)
function:
let excludedAnimals = ["Bulldog", "Labrador"]
return animals.filter({ !excludedAnimals.contains($0) }) // ["Cow"]
The algorithmic complexity of this, however, is O(n×m) where n is the number of elements in the first array and m is the number of elements in the exclusion array. If converting the elements into a Set
, you can get O(n) behavior, since contains(_:)
on Set
is effectively O(1).
let excludedAnimals = Set(arrayLiteral: "Bulldog", "Labrador")
return animals.filter({ !excludedAnimals.contains($0) }) // ["Cow"]
I wouldn’t expect there’d be a ton of value in a function like this specifically, unless it automatically managed the conditional conversion to a Set
in cases where that overhead is expected to be less than the cost of an O(n) contains(_:)
check.
It could be written that way, just as most things could be written via a reduce
, but I think the popularity of this use case (based on those SO questions and my own experience) warrants a more convenient solution. We may also want to make this a lazy sequence, which wouldn't be so trivial for people to do on their own.
Conceptually this would be just a generalization of Set.subtract
https://developer.apple.com/documentation/swift/set/2853597-subtract. I think this would be a convenient utility as a lazy sequence since it is not so trivial to implement by hand and its use is common enough IMO.
One suggestion, is that this issue tracking would not reach to many people because only few watch this repo, so maybe if we want an input from more members of the community an idea would be have a forums thread for it under algorithms topic, if you think is worth it. But it is only a suggestion :)
Quick style note:
let excludedAnimals = Set(arrayLiteral: "Bulldog", "Labrador")
This usually reads better when spelled:
let excludedAnimals: Set = ["Bulldog", "Labrador"]
@lorentey Good point—I had forgotten about that. Thanks!
This is a "subtract" operation, e.g.:
We can see that this is an operation Swift developers are already trying to do from SO questions (1, 2), and it exists in other languages like Ruby.
This is a proposal to get consensus on it. And if people like it, I'd be happy to implement it.