Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.

This is a Jupyter notebook. See How to use these notes.

Sequence length¶

The problem¶

Suppose we have a sequence. How can we find its length. Well if the sequence is represented by a Python list or a Python tuple object, we can just use the len function.

aList = ['r' 'e', 'c', 'u', 'r', 's', 'i', 'o', 'n']
len( aList )

8

aTuple = ('w' 'o', 'n', 'd', 'e', 'r', 'l', 'a', 'n', 'd') ;
len( aTuple )

9

But let's suppose Python didn't have a length function. How can we write one using recursion.

This isn't something I'd normally do, at least not in Python, but the point of these exercises is to get comfortable with recursion, not to learn the best way to solve problems.

A few words about sequences, lists, and tuples¶

Python has several built-in types for representing sequences and more can be added by class defnitions. The built-in types include tuple, list, string, bytes, and bytearray. I'm going to use tuples mostly. To make the code less dependent on the details of Python, we'll make and use the following definitions

def isEmpty( s ):
    """Pre: s is a sequence represented by a tuple
    Post: result is true if s is empty and false otherwise
    """
    assert isinstance(s, tuple)
    return s == ()
def cons( x, s ) :
    """Pre: s is is a sequence represented by a tuple
    Post: result is a sequence represented by a tuple with x as its first item and s as the rest.
    """
    assert isinstance(s, tuple)
    return (x,) + s
def first( s ) :
    """Pre: s is is a nonempty sequence represented by a tuple
    Post: result the first item of the sequence
    """
    assert isinstance(s, tuple) and s != ()
    return s[0] ;
def rest( s ) :
    """Pre: s is is a nonempty sequence represented by a tuple
    Post: result the first item of the sequence
    """
    assert isinstance(s, tuple) and s != ()
    fst, *rst = s
    return tuple(rst);
def decons( s ) :
    """Pre: s is is a nonempty sequence represented by a tuple
    Post: result is a pair consisting of the first items of s and a tuple of the rest of the items
    """
    assert isinstance(s, tuple) and s != ()
    fst, *rst = s
    return fst, tuple(rst)

A contract¶

We write a contract for a length function which will find the length of a sequence represented by a tuple. The contract is

def length( s ):
        """
        Pre: s is a sequence
        Post: result == length of the sequence
        """

Problem analysis¶

Alice's observation¶

Alice notices (rather obviously) that if we split a sequence into its first item and a sequence of all the rest of the items then the length of the list is one more than the length of rest of the sequence. For example if we hae a sequence $[a,b,c,d]$ then and split it into the first item $a$ and the rest of the sequence $[b,c,d]$, the length of the original list will be one more than the length of $[b,c,d]$.

We need a base case¶

The empty sequence can't be split, so it must be a base case.

Your solution¶

Design¶

Based on the problem analysis, we can write a design in pseudocode. In this case the pseudocode will look a lot like Python, so you can take this step if you want or skip it if you don't.

[Put your pseudocode here]

Analyze design¶

Before coding, you should check that your design will work. Here is a checklist

Is every case allowed by the precondition covered?
Does the code do the right thing (i.e. return a result allowed by the postcondition) in each case?
Is there a variant function?

Code¶

Complete the following function

    def length( s ):
        """
        Pre: s is a sequence
        Post: result == length of the sequence
        """

Analyze code¶

If you wrote pseudocode, check that your design is consistant with the pseudocode. If you didn't write pseudocode, use the checklist above to check your code.

Test¶

Below are some tests. After you define the function, you can run these tests and compare the answers with expected answers above.

length( () )

length( (42,) )

length( (6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128,
         2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216 ) )

My Solution¶

Design¶

Here is my pseudocode, it's included here mostly as an illustration of the notation that I use for sequences when writing pseudocode

function $length( s : seq )$

pre $s$ is a sequence
post result is the length of $s$.

if $s = [\,]$ then 0
else $1 + length( s[1,..] )$
end if

or using the functions defined above, we could write

function $length( s : seq )$

pre $s$ is a sequence
post result is the length of $s$.

if $isEmpty(s)$ then 0
else $1 + length( rest(s) )$
end if

Analysis¶

A sequence is either empty or not, so all cases are covered
The code looks right for both cases.
The variant function is the length of the sequence $s$!

Remark. This is an unusual case where the function we are computing and the variant function itself are the same thing. Nevertheless it works.

Code¶

And here is the Python 3 code

 def lengthMine( s ):
        """
        Pre: s is a sequence
        Post: result == length of the sequence
        """
        if isEmpty( s ) : return 0
        else: return 1 + lengthMine( rest( s ) )

Test¶

lengthMine( () )

0

lengthMine( (42,) )

1

lengthMine( (6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128,
         2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216 ) )

10

Disclaimer¶

As mentioned above, this is not a sensible way to find the length of a sequence in Python, given that there is a built in function to do the same thing.