Computation can be thought of as a sequence of states, where there is a meaningful relation between the initial and the final state. Think of summing the first \(n\) positive integers. One strategy is to start with an empty store (or accumulator), and (i) either adding \(n\), then \(n-1\), and so on, to the store until you reach 1; or (ii) adding 1, then 2, and so on, to the store until you reach \(n\), and returning the store at the end.

There is a cyclic pattern in this computation. In each cycle the values of \(n\) and \(store\) change, while the method of computing the next number in the sequence (increasing or decreasing by 1) and the condition on when to stop (\(= 1\) or \(=n\) ) stay constant.

Assume we started the above procedure on number 70. There will be 70 steps in total, until we get the result. Now assume you interrupt the procedure at some point, say after 30 cycles. All the information that you need to be able to continue from there on until the end and return the correct result is called the “state” of the computation at the point of your interruption. In this case, the state consists of the current value of \(n\), the current value of \(store\), how to compute the next number in sequence, and when to stop. The previous values of \(n\) and \(store\) are not relevant, and therefore are not part of the state. We will sometimes use the term “state” to refer only to the parts that may change from cycle to cycle, in this case the current values of \(n\) and \(store\).

Now, a slightly more complicated problem: finding the \(n\)th Fibonacci number. In computing the Fibonacci numbers in a bottom-up iterative manner, we need to keep track of the two previous Fibonacci numbers in order to compute the next one. Therefore, the state of this computation consists of three parts: the current index in the sequence, and the two previous Fibonacci numbers.

You’ve already solved this problem using a while loop. What about solving it using proq_seq from funcutils?

So far, proc_seq has been useful in solving problems where in each cycle you were updating the store which could hold a single number: a sum, max value, and so on. But Fibonacci calls for keeping track of two numbers. This was not a problem in the while loop version since you could name the numbers (e.g. prev and curr).

This brings us to the point where you need a more powerful state. Power in this context means a more sophisticated memory. We will expand our power by introducing the data structure tuple. Tuples are formed by the comma operator, and tuple components are accessed by indexing which starts from 0. Here is how:

>>> t = (3, 5) # A tuple with two components
>>> t
(3, 5)
>>> (1,2) + (3,4) # Tuple concatenation
(1, 2, 3, 4)
>>> k = 1, 2, 3, 4 # A 4-tuple created without parentheses
>>> k[0]
1
>>> k[2]
3
>>> k[9] # IndexError: tuple index out of range

Equipped with tuples, we can now solve the Fibonacci problem using proc_seq.

Try before proceeding.

Here is the solution:

def fibonacci(n):
    """Return the n-th Fibonacci number (n>=1).

    >>> fibonacci(1)
    0
    >>> fibonacci(2)
    1
    >>> fibonacci(8)
    13
    """
    from funcutils import proc_seq
    def increment(x): return x + 1
    def alive(x): return x <= n
    def update(store, n): return (store[1], store[0] + store[1])
    return proc_seq(1, increment, alive, update, (-1,1))[1]

A couple of notes:

  1. Now our store is a tuple of two integers, holding the two previous Fibonacci numbers.
  2. Initializing the store to (-1, 1) is a trick to make the first update produce (1, 0) which corresponds to the first Fibonacci number, and the second update to produce (0,1) as the second Fibonacci number.
  3. In the end, we return the second component of the store which holds the \(n\)th Fibonacci number.

Let’s get back to collatz business for some more fun. First let’s fix some imports for ourselves:

from collatz import collatz
from funcutils import proc_seq

When we were asked to find the largest integer visited in the sequence seeded by n we could solve this problem by:

def largest_in_collatz_sequence(n):
    """Return the largest integer in the Collatz sequence seeded by n. """
    def alive(n): return n > 1
    return proc_seq(n, collatz, alive, max, 0)

Now, assume we are interested in the number of times we change “direction” in a Collatz sequence seeded by \(n\). That is, how many triples of consecutive numbers \((a,b,c)\) are there in the sequence such that \((a > b \land b < c) \lor (a < b \land b >c)\)? Let’s think. What do we have to keep the record of in each iteration to be able to count the direction changes? In each cycle I receive a new number; to be able to tell whether this causes a change in direction, I need to know the previous two numbers. Therefore, my store must hold three numbers: the previous two numbers and the current count of direction changes. Let us first agree on an order. Let the first component of the store be the count, the second two-back, and the third one-back. Now we can write the code:

def collatz_direction_changes(n):
    """Return the number of direction changes in the Collatz sequence seeded by n.

    >>> collatz_direction_changes(8)
    0
    >>> collatz_direction_changes(7)
    9
    """
    def alive(n): return n > 1
    def update(store, new):
        if (store[1] < store[2] and store[2] > new) or (store[1] > store[2] and store[2] < new):
            return (store[0] + 1, store[2], new)
        else:
            return (store[0], store[2], new)
    return proc_seq(n,
                    collatz,
                    alive,
                    update,
                    (0,n,n) # ensure no direction change before the third number
                    )[0]

but we mustn’t. This is too hard to read, it takes to be a genius to understand what the update is doing, so do not even attempt to understand it, unless you are one.

Let’s try to bring some order into this chaos by naming the components of the store in the definition of update:

def collatz_direction_changes(n):
    """Return the number of direction changes in the Collatz sequence seeded by n. """
    def alive(n): return n > 1
    def update(store, new):
        count, two_back, one_back = store # yes, you can unpack a tuple like this
        if (two_back < one_back and one_back > new) or (two_back > one_back and one_back < new):
            return (count + 1, one_back, new)
        else:
            return (count, one_back, new)
    return proc_seq(n, collatz, alive, update, (0, n, n))[0]

This looks better, I think. But I find it very hard to read long lines. Let’s break the if condition into multiple lines. The best way to brake such long lines is to wrap the entire condition expression in parentheses, and when this is done, you can break it anywhere inside the parentheses:

def collatz_direction_changes(n):
    """Return the number of direction changes in the Collatz sequence seeded by n. """
    def alive(n): return n > 1
    def update(store, new):
        count, two_back, one_back = store
        if ((two_back < one_back and one_back > new)
            or 
            (two_back > one_back and one_back < new)):
            return (count + 1, one_back, new)
        else:
            return (count, one_back, new)
    return proc_seq(n, collatz, alive, update, (0, n, n))[0]

Note that this “parenthesize and divide” strategy works for expressions in general.

This is much better. Now, I can read and understand what is going on in the update function without too much effort. But still, this logic of direction change looks a little obtruding (either check the dictionary for “obtruding”, or assume I said “ugly”). The reason is that it violates the principle of “doing one thing at a time” in a function. Let’s outsource this logic to a separate function. Let’s also make it somewhat more clever, or, perhaps, more beautiful. Doing many logical operations does not look nice, does it? Given three numbers, is there an arithmetic way to decide whether there is a directional change or not?

Try before proceeding.

Here is my take, perhaps yours was better:

def turning_point(x,y,z):
    """Retrurn True if y is a turning_point from increasing to decreasing
       or vice versa.

    >>> turning_point(1,2,3)
    False
    >>> turning_point(3,2,1)
    False
    >>> turning_point(1,3,2)
    True
    >>> turning_point(3,1,2)
    True
    >>> turning_point(2,2,3)
    False
    """
    return (z - y) * (y - x) < 0

With this function, we can simplify the update function in collatz_direction_changes:

def collatz_direction_changes(n):
    """Return the number of direction changes in the Collatz sequence seeded by n. """
    def alive(n): return n > 1
    def update(store, new):
        count, two_back, one_back = store
        if turning_point(two_back, one_back, new):
            return (count + 1, one_back, new)
        else:
            return (count, one_back, new)
    return proc_seq(n, collatz, alive, update, (0, n, n))[0]

Well, you guessed it right, we are not done yet.

Let me tell you something useful. You can type-cast booleans to integers by applying the built-in int to any boolean expression. True, 2>1, etc., becomes 1 and False, 2<1, etc., becomes 0.1 Therefore, in incrementing the count according whether you observed a turning point or not, you do not even need an if statement. You can write:

def collatz_direction_changes(n):
    """Return the number of direction changes in the Collatz sequence seeded by n."""
    def alive(n): return n > 1
    def update(store, new):
        count, two_back, one_back = store
        return (count + int(turning_point(two_back, one_back, new)), one_back, new)
    return proc_seq(n, collatz, alive, update, (0, n, n))[0]

That’s the beauty of working with expressions. If the issue is adding 1 to a variable if a certain condition holds and adding 0 if it does not, then simply put an expression that would evaluate to 1 or 0 according to the condition after the + operator. At this point it is enough that you understand why this works. Later on, as more and more practice, you will start seeing such opportunities by yourself.

We have a small computer which we called proc_seq. We were happily (??) solving various problems with it until we realized that its store component can hold only a single number. By enhancing the memory of the store to hold tuples, we were able to solve more complex problems, as we were able to keep track of multiple pieces of information in each cycle of our computations. We used this technology to solve more complex problems like computing Fibonacci numbers and counting direction changes in Collatz sequences. There still remains a limitation in our notion of state which cannot be overcome by increasing the memory of the store component. You will find what it is in another post.

  1. You can map 0 and 1 to False and True respectively by applying the built-in bool to them. Actually bool returns True for any integer other than 0. ↩

You May Also Enjoy

The way of lambda

An introduction to lambda expressions in Python and their use in (functional) programming.

Euclid’s Algorithm

Euclid’s algorithm for finding the greatest common divisor of two integers and its partial proof.