Why does filters in Swift iterate the collection twice?

Question

The following code in Swift's playground or Console App:

let letters = ["A", "B", "C"]

letters.filter({
    (x : String) -> Bool in
    println("PRINT: \(x)")
    return true
})

Prints out:

PRINT: A
PRINT: B
PRINT: C
PRINT: A
PRINT: B
PRINT: C

Why does it iterate over the collection twice?

Is it not the case that the REPL is printing the result of the `filter` method? — The Paramagnetic Croissant, Jun 03 '14 at 21:58
To be fair, the spec of `filter` doesn't specify how many times it executes the closure... — n8gray, Jun 03 '14 at 22:11
There is also a global `filter` method in the header, but I have not figured out how to use it... — matt, Jun 17 '14 at 18:05

score 12 · Accepted Answer · answered Jun 05 '14 at 02:26

12

Most probably filter is implemented to first count the number of elements it needs to store and then, after using that number to size the allocation of storage for a new array, looping again to copy the ones he needs to keep.

The fact that it loops only once if you always return false means that it optimizes away the second cycle iff the result is empty.

You may want to radar this as a bug but it probably is "working as designed": arrays are not lists, after all.

answered Jun 05 '14 at 02:26

Analog File

5,280
20
23

1

Your answer fits the fact so tightly, I am pretty sure that's exactly what happens under the hood. Best reply so far +1. But shouldn't Apple's implementation just allocate a resulting array as big as the source array and then change its capacity at the end? There would be no need to iterate twice. – Jean Le Moignan Jun 13 '14 at 09:39
2

They could. They didn't. It's an implementation choice. Depending on other implementation details it may or may not be the best choice. – Analog File Jun 13 '14 at 19:03

score 7 · Answer 2 · answered Aug 13 '14 at 14:12

7

It is modified in beta 5. It is now traveling only once now, printing ABC instead of ABCABC

answered Aug 13 '14 at 14:12

onevcat

4,591
1
25
31

Jack · Answer 3 · 2014-06-03T22:08:21.530

1

filter returns an array which is being printed out by the playground.

/// Return a Array containing the elements `x` of `self` for which
/// `includeElement(x)` is `true`
func filter(includeElement: (T) -> Bool) -> T[]

I believe the (6 times) is incorrect because if you look below it true only gets returned 3 times.

EDIT: The above is incorrect.

From playing around with it more, I can only say that this is simply the behaviour of the filter function.

letters.reverse().filter({
    (x : String) -> Bool in
    println("PRINT: \(x)")
    return true
})

This prints CBACBA so its simply always traversing the array in order, twice.

letters.filter({
        (x : String) -> Bool in
        println("PRINT: \(x)")
        if (x == "A") {
           return true
        }
        return false
    })

This still prints ABCABC, so go figure..

I'll go ask a Swift engineer in a bit and get back to you on why this is! (If they know :p)

edited Jun 03 '14 at 22:08

answered Jun 03 '14 at 21:59

Jack

16,677
8
47
51

It's the same result in a Console Application as well, I've updated the example to show that it's the `println` that's getting called twice for each item – mythz Jun 03 '14 at 22:01
@mythz Ah you are right, my answer is incorrect. Let me dig into it a bit though – Jack Jun 03 '14 at 22:03
@mythz I know you're right because if you add another `println` right below the previous one the output is `AABBCCAABBCC` – Jack Jun 03 '14 at 22:04
1

Curiously enough, it only runs it once each if you always `return false` – Tim Jun 03 '14 at 22:07

Why does filters in Swift iterate the collection twice?

3 Answers3

Linked