Testing if some value is not produced by an iterator

Question

I would like to test whether a certain value belongs to a sequence of numbers, which is produced using an iterator. Of course when the value does belong to the sequence, one can stop as soon as the value is met. But when it does not, I guess that's when problems show up.

However one can use additional information (e.g., the sequence is increasing).

Consider the Fibonacci example:

class FibonacciIterator(object):
    def __init__(self):
        self.mem = [0, 1]
    def __next__(self):
        curr = self.mem[0]
        new = self.mem[0]+self.mem[1]
        self.mem[0] = self.mem[1]
        self.mem[1] = new
        return curr

class Fibonacci(object):
    def __iter__(self):
       return FibonacciIterator()

If one tests whether 8 belongs to the sequence then everything is fine:

>>> fib = Fibonacci()
>>> 8 in fib
True

If, however, one tests 10 (which doesn't belong to the sequence) then

>>> 10 in fib
...

never terminates. But one could easily determine that 10 is not in the sequence by observing that after 8 comes 13, and since the sequence is increasing then necessarily not 10 in fib.

Is there a nice way in Python to implement such behavior of in, so that 10 in fib terminates?

You can provide a definition of `__contains__` that knows that the sequence is monotonically increasing. However, for a generator, `__contains__` would *consume* the sequence, so it may not be particularly useful. — chepner, Jul 08 '17 at 12:48
seems like a problem where you are not testing weather the number has exceeded the input — Shubham Srivastava, Jul 08 '17 at 12:50
@chepner that's indeed the way: the fact that the iterator gets consumed is not a big deal in my example above, since I would define `__contains__` in the `Fibonacci` class (the "iterable") to produce a new `FibonacciIterator` (the "iterator") every time `in` is used — Lorenzo Stella, Jul 08 '17 at 13:10

score 1 · Accepted Answer · answered Jul 08 '17 at 13:57

The trivial solution would be to implement a __contains__ method that just iterates over a copy of the iterator:

class FibonacciIterator(object):
    def __init__(self):
        self.mem = [0, 1]

    def __iter__(self):
        return self

    def __contains__(self, value):
        testit = FibonacciIterator()
        testit.mem = list(self.mem)  # copy
        for item in testit:
            if item == value:
                return True
            if item > value:
                return False

    def __next__(self):
        curr = self.mem[0]
        self.mem = self.mem[1], sum(self.mem)
        return curr

class Fibonacci(object):
    def __iter__(self):
        return FibonacciIterator()

    def __contains__(self, value):
        return value in iter(self)

However there is another way to determine if a number is a Fibonacci number: If either (5*n**2 + 4) or (5*n**2 – 4) or both are perfect squares (square of an integer).

I'll use the approach from this answer to implement the is_square function:

def is_square(apositiveint):
    # Source: https://stackoverflow.com/a/2489519/5393381
    # Credit: Alex Martelli

    x = apositiveint // 2
    seen = {x}
    while x * x != apositiveint:
        x = (x + (apositiveint // x)) // 2
        if x in seen: 
            return False
        seen.add(x)
    return True

class FibonacciIterator(object):
    def __init__(self):
        self.mem = [0, 1]

    def __iter__(self):
        return self

    def __contains__(self, value):
        if value < self.mem[0]:
            return False
        else:
            # Just check if at least one of both is a perfect square
            value_squared_times_five = 5*value**2
            return is_square(value_squared_times_five + 4) or is_square(value_squared_times_five - 4)

    def __next__(self):
        curr = self.mem[0]
        self.mem = self.mem[1], sum(self.mem)
        return curr

class Fibonacci(object):
    def __iter__(self):
        return FibonacciIterator()

    def __contains__(self, value):
        return value in iter(self)

Testing if some value is not produced by an iterator

1 Answers1