# How to effectively filter array by another array? ( In functional paradigm )

**URL:** <https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442>\
**Category:** Using Swift\
**Created:** [February 13, 2019, 3:58pm UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442 "2019-02-13T15:58:53Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![lolgear](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lolgear/32/4790_2.png) [@lolgear](https://forums.swift.org/u/lolgear)\
**Post date:** [February 13, 2019, 3:58pm UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/1 "2019-02-13T15:58:53Z")

</div>

Consider following task.

Let A be a list of `Comparable` items. Let B be a list of `Comparable` items. Entries in these lists can be compared.

Output is a list of entries in A that are not in the list B.

Two conditions.

1. Assume A and B are sorted.
2. Count of the same entries are considered as difference of count in A and count in B. Output duplicates respectively to this difference if it is greater than zero. Otherwise, skip them.

Example:  
A = [1, 1, 1, 2, 4, 7]  
B = [1, 2, 2, 4, 6]

Output:  
[1, 1, 7]

Description:  
A has three 1, one 2.  
B has one 1, two 2.

Result has three - one 1 and one - two 2.  
Result has two 1 and (-1) 2.  
Result has two 1.

Functional condition:

1. Do it without loops.

Try to solve this task for different count ( 900 - 100\_000 )

I am asking for effective (tail call optimized) solution.  
Is it possible?

```swift
func generateArray(count: UInt = 900, range: UInt = 1000) -> [UInt] {
    return Array(0..<count).map{ _ in return UInt.random(in: 0...range) }
}

func test_ListsDifference() {
    let count = 10_000
    let a = generateArray(count: count).sorted()
    let b = generateArray(count: count).sorted()
    
    var result = [UInt]()
    self.measure {
        result = rejecting(a, b)
    }
}

```

My dirty solution so far

```swift
func rejecting(_ a: ArraySlice<T>, _ b: ArraySlice<T>) -> ArraySlice<T> {
  func _rejecting(_ a: ArraySlice<T>, _ b: ArraySlice<T>, aStart: ArraySlice<T>.Index, bStart: ArraySlice<T>.Index) -> ArraySlice<T> {
    if aStart == a.endIndex {
      return []
    }
    else if bStart == b.endIndex {
      return a[aStart..<a.endIndex]
    }
    else if a[aStart] == b[bStart] {
      return _rejecting(a, b, aStart: aStart.advanced(by: 1), bStart: bStart.advanced(by: 1))
    }
    else if a[aStart] > b[bStart] {
      return _rejecting(a, b, aStart: aStart, bStart: bStart.advanced(by: 1))
    }
    else {
      return _rejecting(a, b, aStart: aStart.advanced(by: 1), bStart: bStart)
    }
  }
  return _rejecting(a, b, aStart: a.startIndex, bStart: b.startIndex)
}

```

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [February 13, 2019, 5:19pm UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/2 "2019-02-13T17:19:40Z")

</div>

Your code doesn’t work so I just did some clean up:

```swift
func rejecting<T>(_ a: [T], _ b: [T]) -> [T] where T: Comparable {
    func _rejecting(_ a: ArraySlice<T>, _ b: ArraySlice<T>) -> [T] {
        guard let firstA = a.first,
            let firstB = b.first else {
                return Array(a)
        }
        if firstA < firstB {
            return [firstA] + _rejecting(a.dropFirst(), b)
        }
        if firstA > firstB {
            return _rejecting(a, b.dropFirst())
        }
        return _rejecting(a.dropFirst(), b.dropFirst())
    }
    return _rejecting(a[...], b[...])
}

```

Though I don’t know if Swift already support tco.

---

<div class="post-metadata">

**Author:** ![lolgear](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lolgear/32/4790_2.png) [@lolgear](https://forums.swift.org/u/lolgear)\
**Post date:** [February 13, 2019, 5:32pm UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/3 "2019-02-13T17:32:58Z")

</div>

Your example is not tco at all.  
How can compiler optimize it in case of this branch?

```swift
if firstA < firstB {
    return [firstA] + _rejecting(a.dropFirst(), b)
}

```

My idea was ( and is ) keep slices immutable. ( and also use accumulator for result for TCO ).

Consider next enhancement.

```swift
func rejecting(_ a: ArraySlice<T>, _ b: ArraySlice<T>) -> ArraySlice<T> {
  func _rejecting(_ a: inout ArraySlice<T>, _ b: inout ArraySlice<T>, aStart: ArraySlice<T>.Index, bStart: ArraySlice<T>.Index, result: [T]) -> [T] {
    if aStart == a.endIndex || bStart == b.endIndex {
        return result.appending(a[aStart...])
    }
    return _rejecting(&a, &b, aStart: aStart.advanced(by: a[aStart] <= b[bStart] ? 1 : 0), bStart: bStart.advanced(by: a[aStart] >= b[bStart] ? 1 : 0), result: a[aStart] < b[bStart] ? result.appending(a[aStart]) : result )
  }
  var inoutA = a
  var inoutB = b
  return ArraySlice(_rejecting(&inoutA, &inoutB, aStart: a.startIndex, bStart: b.startIndex, result: []))
}

```

And related extension on Array.

```swift
extension Array where Element: Comparable {
  func appending(_ a: Element) -> Array {
    return self + [a]
  }
  func appending(_ s: [Element]) -> Array {
    return self + s
  }
  func appending(_ as: ArraySlice<Element>) -> Array {
    return self + `as`
  }
}

```

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [February 13, 2019, 5:56pm UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/4 "2019-02-13T17:56:08Z")

</div>

The name for this operation is “symmetric difference”.

Edit: My mistake, it is subtraction. Thanks @mayoff

---

<div class="post-metadata">

**Author:** ![mayoff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/mayoff/32/613_2.png) [@mayoff](https://forums.swift.org/u/mayoff)\
**Post date:** [February 13, 2019, 6:00pm UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/5 "2019-02-13T18:00:25Z")

</div>

The symmetric difference would include elements of B that are not in A. The algorithm described by lolgear does not include such elements.

---

<div class="post-metadata">

**Author:** ![mayoff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/mayoff/32/613_2.png) [@mayoff](https://forums.swift.org/u/mayoff)\
**Post date:** [February 13, 2019, 6:29pm UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/6 "2019-02-13T18:29:51Z")

</div>

Your demand is that the function be [written recursively, but execute iteratively](http://sarabander.github.io/sicp/html/1_002e2.xhtml#g_t1_002e2_002e1) (to handle large inputs on real hardware), by way of tail call optimization. Your demand has a fundamental problem.

The problem is that Swift is not Scheme. Scheme guarantees tail call optimization, but Swift does not. Tail call optimization that's not guaranteed to occur [is not a programming model](https://pharr.org/matt/blog/2018/04/18/ispc-origins.html#auto-vectorization-is-not-a-programming-model).

Since Swift uses automatic reference counting, it's often the case that Swift has to generate some clean-up reference count adjustments after a call that appears to be in tail position. These adjustments prevent the apparent tail call from being optimized.

Even if you play around for a while and discover a way to implement the algorithm recursively that Swift then compiles with tail call optimization, it's dangerous to rely on it. Slight changes in a future version of the compiler might no longer optimize the tail calls in your carefully-tuned function.

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [February 13, 2019, 6:41pm UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/7 "2019-02-13T18:41:33Z")

</div>

Yea yea, I was a little light headed when I was writing it, my bad 😛.

Just want to point out that you forgot accumulator, which in any case added in your next iteration.

---

<div class="post-metadata">

**Author:** ![mayoff](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/mayoff/32/613_2.png) [@mayoff](https://forums.swift.org/u/mayoff)\
**Post date:** [February 13, 2019, 6:44pm UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/8 "2019-02-13T18:44:52Z")

</div>

This, by the way, was my attempt at getting Swift to apply tail-call optimization, but it still wouldn't do it:

```
extension Collection where Element: Comparable {
    func removing<C2: Collection>(contentsOf you: C2) -> [Element] where C2.Element == Element {
        var output: [Element] = []

        func remove(mine: Index, yours: C2.Index) {
            if mine == endIndex {
                // I have no more elements. There's no need to look at the rest of yours.
                return
            }

            else if yours == you.endIndex {
                // You have no more elements. All the rest of mine are included.
                return output.append(contentsOf: self[mine...])
            }

            else if self[mine] < you[yours] {
                output.append(self[mine])
                return remove(mine: self.index(after: mine), yours: yours)
            }

            else if you[yours] < self[mine] {
                return remove(mine: mine, yours: you.index(after: yours))
            }

            else /* self[mine] == you[yours] */ {
                return remove(mine: self.index(after: mine), yours: you.index(after: yours))
            }
        }

        remove(mine: self.startIndex, yours: you.startIndex)
        return output
    }
}

```

It ends up with non-optimized recursive calls that look like this:

```
    0x100001af4 <+260>: movzx esi, al
    0x100001af7 <+263>: mov rdi, r15
    0x100001afa <+266>: mov rdx, rbx
    0x100001afd <+269>: mov r8, r14
    0x100001b00 <+272>: mov r9, r12
    0x100001b03 <+275>: call 0x1000019f0 ; <+0> at main.swift:36
-> 0x100001b08 <+280>: add rsp, 0x48
    0x100001b0c <+284>: pop rbx
    0x100001b0d <+285>: pop r12
    0x100001b0f <+287>: pop r13
    0x100001b11 <+289>: pop r14
    0x100001b13 <+291>: pop r15
    0x100001b15 <+293>: pop rbp
    0x100001b16 <+294>: ret    

```

The only cleanup being done after the recursive call is restoring `rsp` and callee-saved registers. No arguments are passed on the stack. As far as I can tell, the cleanup could be done before the recursive call, but the compiler isn't smart enough to do it.

---

<div class="post-metadata">

**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\
**Post date:** [February 16, 2019, 1:37am UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/9 "2019-02-16T01:37:33Z")

</div>

Since you are extracting elements from the source and filter each one at a time and always in order, it seemed that the iterator interface would be perfect. Instead of putting it here, I put [my version in a gist](https://gist.github.com/CTMacUser/c8b016d22cd4d83d9f4e60cb81eb99b8#file-basicsetsubtraction-swift). But I'll copy the business method here:

```
extension SetSubtractionIterator: IteratorProtocol {

    public mutating func next() -> Base.Element? {
        // Can't return wrapped element if there's no more.
        lastBase = lastBase ?? base.next()
        guard let latestBase = lastBase else { return nil }

        /*
         Compare latest from base and filtered:

         - filtered is NIL: return base and increment it
         - base < filtered: return base and increment it
         - base == filtered: increment both then recursive call
         - base > filtered: increment filter then recursive call
         */
        do {
            let incrementBase: Bool
            defer {
                if incrementBase {
                    lastBase = base.next()
                    if let nextBase = lastBase, nextBase < latestBase {
                        preconditionFailure("To-be-filtered sequence isn't actually sorted")
                    }
                }
            }

            lastFilter = lastFilter ?? filters.next()
            guard let latestFilter = lastFilter, latestBase >= latestFilter else {
                incrementBase = true
                return latestBase
            }
            defer {
                lastFilter = filters.next()
                if let nextFiltered = lastFilter, nextFiltered < latestFilter {
                    preconditionFailure("Filtering sequence isn't actually sorted")
                }
            }

            incrementBase = latestBase == latestFilter
        }
        return next()
    }

}

```

I had to put the bulk of the code in a `do`-block, [otherwise I'll get infinite recursion](https://forums.swift.org/t/how-is-defer-timed-with-recursive-calls/20552). Could someone check if it generates the sought-after tail-recursion?

Since I qualified the array requirements as small as possible, this code will even work with single-pass `Sequence`s. It helps here that you require `<`; using a general predicate would change how the comparisons are done, need to check for exceptions, and probably need eager/lazy versions. Maybe I'll try that later; it'd need Swift 5's `Result` to generalize it to one copy of the algorithm.

---

<div class="post-metadata">

**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\
**Post date:** [February 16, 2019, 1:47am UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/10 "2019-02-16T01:47:00Z")

</div>

Oh, I forgot examples:

```
let x = [1, 1, 1, 2, 4, 7]
Array(x.subtract(sortedFilterElements: [1, 2, 2, 4, 6])) // [1, 1, 7]
Array(x.subtract(sortedFilterElements: [1, 4, 7])) // [1, 1, 2]
Array(x.subtract(sortedFilterElements: EmptyCollection())) // [1, 1, 1, 2, 4, 7]
Array(EmptyCollection().subtract(sortedFilterElements: [1, 2, 2, 4, 6])) // []

```

---

<div class="post-metadata">

**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\
**Post date:** [February 20, 2019, 5:28am UTC](https://forums.swift.org/t/how-to-effectively-filter-array-by-another-array-in-functional-paradigm/20442/11 "2019-02-20T05:28:29Z")

</div>

I [updated the gist with a new implementation in a different file](https://gist.github.com/CTMacUser/c8b016d22cd4d83d9f4e60cb81eb99b8#file-setsubtraction-swift). I tried putting all to core functionality in a single function, but I couldn't do that for the `Collection` adaptation. If any of you want to see if the implementations are loop-less-ly recursive, you need to check both `FullSetSubtractionImplementationIterator.next()` and `LazyPresortedSubtractionCollection.nextIndex(baseStart: filterStart:)`.

I tried to make a `BidirectionalCollection` extension, but trying to figure out the synchronization between the main and filter collections in reverse is too hard. I don't feel like taking a couple weeks figuring it out. From what I tried, I think it's most likely possible, though. (In forward iteration, `endIndex` can be a general guess, but I reimplemented it in the BC extension to get the precise answer since I assume such an answer during `index(before:)`. Note said re-extension is linear instead of constant, just like `startIndex`.)