Guarding against an empty sequence


(Adriano Ferreira) #1

Hi everyone!

I’m working on the following method:

extension SequenceType {

    /// Check if `predicate` is true for all elements of `self`
    ///
    /// - Parameter predicate: The predicate called on each element of `self`
    ///
    /// - Returns: True iff every element in `self` satisfies `predicate`, false otherwise

    @warn_unused_result
    func all(@noescape where predicate: Generator.Element throws -> Bool) rethrows -> Bool {
        for element in self where try !predicate(element) {
            return false
        }

        return true
    }
}

However, when the sequence is empty the method returns true, which is not the desired behaviour.

let a = [Int]()
let b = a.all(where: { $0 > 7 })
XCTAssertFalse(b) // This fails, cause there’s no guard against an empty sequence

Does anyone know how to guard against an empty sequence?

I’m using Xcode 7.3.1 and Swift 2.2.

Best,

— A


(Jacob Bandes-Storch) #2

I'd argue that this behavior is correct. By extension of De Morgan's laws
<https://en.wikipedia.org/wiki/De_Morgan's_laws>, "seq.all { pred($0) }"
should be equivalent to "!seq.contains { !pred($0) }".

Jacob

···

On Sun, May 8, 2016 at 7:16 PM, Adriano Ferreira via swift-users < swift-users@swift.org> wrote:

Hi everyone!

I’m working on the following method:

extension SequenceType {

    /// Check if `predicate` is true for all elements of `self`
    ///
    /// - Parameter predicate: The predicate called on each element of
`self`
    ///
    /// - Returns: True iff every element in `self` satisfies
`predicate`, false otherwise

    @warn_unused_result
    func all(@noescape where predicate: Generator.Element throws -> Bool)
rethrows -> Bool {
        for element in self where try !predicate(element) {
            return false
        }

        return true
    }
}

However, when the sequence is empty the method returns true, which is not
the desired behaviour.

let a = [Int]()
let b = a.all(where: { $0 > 7 })
XCTAssertFalse(b) // This fails, cause there’s no guard against an
empty sequence

Does anyone know how to guard against an empty sequence?

I’m using Xcode 7.3.1 and Swift 2.2.

Best,

— A

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Shane S) #3

I imagine `#underestimateCount()` is going to be your best bet, though you may not always see the results you desire

some notes:

1. most would argue that the results you are describing are correct: it is vacuously true that for an empty sequence _every_ element in the sequence will satisfy any predicate you give it

2. do you have the option to constrain this to CollectionType instead?

3. one option would be for you to grab the generator and iteratively send it `next()` on your own - that way you could check if it returns `nil` the first time that you call it (i.e. the sequence is empty) and return whatever you desire in that case

— Shane S

···

On May 8, 2016, at 7:16 PM, Adriano Ferreira via swift-users <swift-users@swift.org<mailto:swift-users@swift.org>> wrote:

Hi everyone!

I’m working on the following method:

extension SequenceType {

    /// Check if `predicate` is true for all elements of `self`
    ///
    /// - Parameter predicate: The predicate called on each element of `self`
    ///
    /// - Returns: True iff every element in `self` satisfies `predicate`, false otherwise

    @warn_unused_result
    func all(@noescape where predicate: Generator.Element throws -> Bool) rethrows -> Bool {
        for element in self where try !predicate(element) {
            return false
        }

        return true
    }
}

However, when the sequence is empty the method returns true, which is not the desired behaviour.

let a = [Int]()
let b = a.all(where: { $0 > 7 })
XCTAssertFalse(b) // This fails, cause there’s no guard against an empty sequence

Does anyone know how to guard against an empty sequence?

I’m using Xcode 7.3.1 and Swift 2.2.

Best,

— A
_______________________________________________
swift-users mailing list
swift-users@swift.org<mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users


(Erica Sadun) #4

I know this is completely not answering your question, but why wouldn't an empty sequence return true? There is no element in an empty sequence that does not satisfy the predicate.

As for guarding against an empty sequence, you can create a buffered sequence type with 1-lookahead. Off the top of my head, n o guarantees for correctness:

public struct BufferedSequence<Base : SequenceType>:GeneratorType, SequenceType {
    
    internal var _base: Base
    internal var _generator: Base.Generator
    public var bufferedElement: Base.Generator.Element?
    
    public init(_ base: Base) {
        _base = base
        _generator = base.generate()
        bufferedElement = _generator.next()
    }

    public mutating func next() -> Base.Generator.Element? {
        defer {
            if bufferedElement != nil {
                bufferedElement = _generator.next()
            }
        }
        return bufferedElement
    }
    
    public func isEmpty() -> Bool {
        return bufferedElement == nil
    }
}

-- E

···

On May 8, 2016, at 8:16 PM, Adriano Ferreira via swift-users <swift-users@swift.org> wrote:

Hi everyone!

I’m working on the following method:

extension SequenceType {

    /// Check if `predicate` is true for all elements of `self`
    ///
    /// - Parameter predicate: The predicate called on each element of `self`
    ///
    /// - Returns: True iff every element in `self` satisfies `predicate`, false otherwise

    @warn_unused_result
    func all(@noescape where predicate: Generator.Element throws -> Bool) rethrows -> Bool {
        for element in self where try !predicate(element) {
            return false
        }

        return true
    }
}

However, when the sequence is empty the method returns true, which is not the desired behaviour.

let a = [Int]()
let b = a.all(where: { $0 > 7 })
XCTAssertFalse(b) // This fails, cause there’s no guard against an empty sequence

Does anyone know how to guard against an empty sequence?

I’m using Xcode 7.3.1 and Swift 2.2.

Best,

— A
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Jeremy Pereira) #5

I would agree with everybody else who says an empty sequence should return true (and your documentation comment seems to confirm that). However, to implement the behaviour you want, there is no need to think of something clever, simply count the number of iterations of the for loop.

    func all(@noescape where predicate: Generator.Element throws -> Bool) rethrows -> Bool {
  var count = 0
        for element in self {
      guard try predicate(element) else { return false }
      count += 1
        }
        return count > 0
    }

YMMV, but I think the above (even without the count) is more readable than the original version with the where clause because it is more explicit about how the algorithm works.

Obviously “count” could be a boolean that starts out false and gets set to true on each iteration after the guard and I know you don’t like the idea, but it is cleaner and simpler than mucking about with explicitly calling next() or creating a whole new buffered sequence just to avoid two lines of code.

···

On 9 May 2016, at 03:16, Adriano Ferreira via swift-users <swift-users@swift.org> wrote:

Hi everyone!

I’m working on the following method:

extension SequenceType {

    /// Check if `predicate` is true for all elements of `self`
    ///
    /// - Parameter predicate: The predicate called on each element of `self`
    ///
    /// - Returns: True iff every element in `self` satisfies `predicate`, false otherwise

    @warn_unused_result
    func all(@noescape where predicate: Generator.Element throws -> Bool) rethrows -> Bool {
        for element in self where try !predicate(element) {
            return false
        }

        return true
    }
}

However, when the sequence is empty the method returns true, which is not the desired behaviour.

let a = [Int]()
let b = a.all(where: { $0 > 7 })
XCTAssertFalse(b) // This fails, cause there’s no guard against an empty sequence

Does anyone know how to guard against an empty sequence?

I’m using Xcode 7.3.1 and Swift 2.2.

Best,

— A
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Adriano Ferreira) #6

Hi all, thanks for the replies.

So, I thought about “underestimatedCount” but was not sure how to use it properly.

I chose to put this method on SequenceType rather than CollectionType because I’d like it to be less restrictive since there was no need to subscripting.

Also, about using “next”, Austin mentioned something interesting:

“… a sequence might actually be a sequence of n random numbers coming out of a PRNG; checking for 'emptiness' by calling 'next' would consume a random number that you couldn't ever get back, even if you called 'next' again using a different generator.”

So far, I have a mixed feeling about using a boolean to track whether or not the loop has even been executed.

I wonder why there’s no simple way (or I’m overlooking it) to check if a sequence is empty.

Any other suggestions?

Cheers,

— A

···

On May 8, 2016, at 11:42 PM, Shane S <electro_alchemy@hotmail.com> wrote:

I imagine `#underestimateCount()` is going to be your best bet, though you may not always see the results you desire

some notes:

1. most would argue that the results you are describing are correct: it is vacuously true that for an empty sequence _every_ element in the sequence will satisfy any predicate you give it

2. do you have the option to constrain this to CollectionType instead?

3. one option would be for you to grab the generator and iteratively send it `next()` on your own - that way you could check if it returns `nil` the first time that you call it (i.e. the sequence is empty) and return whatever you desire in that case

— Shane S

On May 8, 2016, at 7:16 PM, Adriano Ferreira via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:

Hi everyone!

I’m working on the following method:

extension SequenceType {

    /// Check if `predicate` is true for all elements of `self`
    ///
    /// - Parameter predicate: The predicate called on each element of `self`
    ///
    /// - Returns: True iff every element in `self` satisfies `predicate`, false otherwise

    @warn_unused_result
    func all(@noescape where predicate: Generator.Element throws -> Bool) rethrows -> Bool {
        for element in self where try !predicate(element) {
            return false
        }

        return true
    }
}

However, when the sequence is empty the method returns true, which is not the desired behaviour.

let a = [Int]()
let b = a.all(where: { $0 > 7 })
XCTAssertFalse(b) // This fails, cause there’s no guard against an empty sequence

Does anyone know how to guard against an empty sequence?

I’m using Xcode 7.3.1 and Swift 2.2.

Best,

— A
_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users


(Shane S) #7

So, I thought about “underestimatedCount” but was not sure how to use it properly.

`guard self.underestimateCount > 0 else {return false}`

Also, about using “next”, Austin mentioned something interesting:

“… a sequence might actually be a sequence of n random numbers coming out of a PRNG; checking for 'emptiness' by calling 'next' would consume a random number that you couldn't ever get back, even if you called 'next' again using a different generator.”

the `for … each` enumeration in the body of your function also consumes the elements of your sequence :slight_smile: so I assumed that was an acceptable consequence of applying this function

if you’re thinking specifically about checking the first value returned by `next()` for nil and then no longer having it available to test against your predicate, then I was thinking roughly along the lines of something like:

var generator = self.generate()
var isPredicateSatisfiedForAllElements = false

while let element = generator.next() {
  isPredicateSatisfiedForAllElements = try predicate(element)
  if !isPredicateSatisfiedForAllElements {break}
}

return isPredicateSatisfiedForAllElements

— Shane S

···

On May 9, 2016, at 6:18 AM, Adriano Ferreira <adriano.ferreira@me.com<mailto:adriano.ferreira@me.com>> wrote:

On May 8, 2016, at 11:42 PM, Shane S <electro_alchemy@hotmail.com<mailto:electro_alchemy@hotmail.com>> wrote:

I imagine `#underestimateCount()` is going to be your best bet, though you may not always see the results you desire

some notes:

1. most would argue that the results you are describing are correct: it is vacuously true that for an empty sequence _every_ element in the sequence will satisfy any predicate you give it

2. do you have the option to constrain this to CollectionType instead?

3. one option would be for you to grab the generator and iteratively send it `next()` on your own - that way you could check if it returns `nil` the first time that you call it (i.e. the sequence is empty) and return whatever you desire in that case

— Shane S

On May 8, 2016, at 7:16 PM, Adriano Ferreira via swift-users <swift-users@swift.org<mailto:swift-users@swift.org>> wrote:

Hi everyone!

I’m working on the following method:

extension SequenceType {

    /// Check if `predicate` is true for all elements of `self`
    ///
    /// - Parameter predicate: The predicate called on each element of `self`
    ///
    /// - Returns: True iff every element in `self` satisfies `predicate`, false otherwise

    @warn_unused_result
    func all(@noescape where predicate: Generator.Element throws -> Bool) rethrows -> Bool {
        for element in self where try !predicate(element) {
            return false
        }

        return true
    }
}

However, when the sequence is empty the method returns true, which is not the desired behaviour.

let a = [Int]()
let b = a.all(where: { $0 > 7 })
XCTAssertFalse(b) // This fails, cause there’s no guard against an empty sequence

Does anyone know how to guard against an empty sequence?

I’m using Xcode 7.3.1 and Swift 2.2.

Best,

— A
_______________________________________________
swift-users mailing list
swift-users@swift.org<mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users


(Dmitri Gribenko) #8

`underestimateCount` is what it says, an underestimate. A non-empty
sequence can return 0.

Dmitri

···

On Mon, May 9, 2016 at 8:21 AM, Shane S via swift-users <swift-users@swift.org> wrote:

On May 9, 2016, at 6:18 AM, Adriano Ferreira <adriano.ferreira@me.com> > wrote:

So, I thought about “underestimatedCount” but was not sure how to use it
properly.

`guard self.underestimateCount > 0 else {return false}`

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/