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

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

To make the code less dependent on the details of Python, we'll make and use the following definitions.

In [40]:

```
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 empty():
"""Pre: true
Post: result is an empty sequence"""
return ()
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)
def split( s ) : # Split a sequence into two roughly equal parts.
"""Pre: s is is a sequence represented by a tuple
Post: result is a pair consisting of the first two tuples, which if catentated form the origninal tuple.
The two parts will be the same size or differ in size by one.
Consequence: If s is of size at least 2, the two tuples will each be smaller than s.
"""
assert isinstance(s, tuple)
l = len(s)
return s[0:l//2], s[l//2:]
def cat( s, t ) : # Concatenate two sequences
"""Pre: s and t are sequences represented by a tuple
Post: result is a tuple formed by concatenating s with t.
"""
assert isinstance(s, tuple) and isinstance(t, tuple)
return s+t
```

We write a contract for a `count`

function which count the number of times an item equal to x occurs in a sequence x

```
def best( s, x ):
"""
Pre: s is a sequence
Post: result == number of items in s equal to x
"""
```

*[Put your problem analysis here.]*

*[What is the base case?]*

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]*

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?

Complete the following function

In [18]:

```
def count( s, x ):
"""
Pre: s is a sequence
Post: result == number of items in s equal to x
"""
```

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.

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

In [19]:

```
count( (), 0 ) # Expect 0
```

In [20]:

```
count( (0,), 0) # Expect 1
```

In [21]:

```
count( (1,), 0) # Expect 0
```

In [22]:

```
count( (1,2,0,1,2,3,0,1), 1) # Expect 3
```

In [23]:

```
count( (1,2,0,1,2,3,0,1), 0) # Expect 2
```

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

function$count\langle T\rangle( s : Seq\langle T\rangle, T x)$

pre$s$ is a sequence

postresult is number of items in $s$ equal to $x$

if$s = [\,]$then0

elsif$s(0)=x$then$1 + count( s[1,..] )$

else$count( s[1,..] )$end if

- 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$!

And here is the Python 3 code

In [24]:

```
def countMine( s, x ):
"""
Pre: s is a sequence
Post: result == number of items in s equal to x
"""
if isEmpty(s) : return 0
elif first(s) == x : return 1 + countMine( rest(s), x)
else:return countMine( rest(s), x)
```

In [25]:

```
countMine( (), 0 ) # Expect 0
```

Out[25]:

In [26]:

```
countMine( (0,), 0) # Expect 1
```

Out[26]:

In [27]:

```
countMine( (1,), 0) # Expect 0
```

Out[27]:

In [28]:

```
countMine( (1,2,0,1,2,3,0,1), 1) # Expect 3
```

Out[28]:

In [29]:

```
countMine( (1,2,0,1,2,3,0,1), 0) # Expect 2
```

Out[29]: