Skip to content

Inductive Sequence

Learning Objectives

At the end of this sub-unit, students should

  • understand the inductive definition of sequence.
  • know how to work with sequence recursively.

Inductive Definition

We have a definition of list as a mutable sequence of anything. However, this definition does not make it easy for us to work with recursion. We can --of course-- simply use the translation from iteration to recursion that we had before. But there are several pre-processing we need to do before we can make the translation. Let us illustrate the pre-processing with a simple problem of reversing a sequence. In this case, our sequence is a list, but a simple modification to tuple can be done.

1
2
3
4
5
6
7
def reverse(lst):
  res = []
  for elem in lst:
    # simple, but elem cannot be used for translation
    # so we need to remove the use of elem
    res = [elem] + res
  return res

1
2
3
4
5
6
7
def reverse(lst):
  res = []
  while len(lst) > 0:
    res = [lst[0]] + res
    # now that we have taken the first element, we need to remove it via slicing
    lst = lst[1:]
  return res

1
2
3
4
5
6
7
def reverse(lst):
  res = []                 # base value
  while len(lst) > 0:      # base case: not (len(tpl > 0))
    res = [lst[0]] + res  # deferred operation
    # now that we have taken the first element, we need to remove it via slicing
    lst = lst[1:]          # next argument
  return res

1
2
3
4
5
6
7
def reverse(lst):
  if not (len(lst) > 0):
    return []
  else:
    # we need to put lst[0] at the back
    # because we are reversing it
    return reverse(lst[1:]) + [lst[0]]

1
2
3
4
5
6
7
def reverse(lst):
  if len(lst) == 0:  # since it cannot have negative length
    return []
  else:
    # we need to put lst[0] at the back
    # because we are reversing it
    return reverse(lst[1:]) + [lst[0]]

This simple translation reveals quite a number of interesting concepts.

  • If we define a list as a mutable sequence of anything, what is the type of sequence after we remove the first element using lst[1:]?
    • It is still a list.
  • If reverse(lst) is always returning the reverse of a list lst, what is the result for empty list?
    • Also an empty list.
  • What is the type of sequence that is an empty list?
    • It is still a list.

So we can see that we can redefine a list as follows.

Inductive List

A list is either one of the following and nothing else.

  • An empty list.
  • An item (i.e., the first item) followed by a list without the first item.

It is often useful to have a shorthand notation for this. We can abuse our type annotation from before and write a list as follows.

1
2
list :: []
     :: [item] ++ list

Here, the ++ is our own convention of a concatenation.

Notice how list appears in both the left and the side of the ::. This means that we define a list using a list. Does this remind you of something? This looks exactly like the structure of the recursion that we have before.

1
2
list :: []              # base case: len(lst) == 0
     :: [item] ++ list  # recursive: lst[0] and rec(lst[1:])

So inductive definition can be directly translated to a recursive code. This is the reason why we want to represent a list inductively. We can try to use this new knowledge of inductive list to write recursive codes.

Mathematical Induction

The general concept is called structural induction and usually used to prove certain properties. If you have encountered mathematical induction in high-school before, it is typically represented as follows.

  • Proof for \(P(0)\).
  • Assume the predicate is true for \(P(n)\), we proof for \(P(n + 1)\).

This is often represented as building a ladder. If we have the first ladder \(P(0)\), we can start climbing. Assuming that we have a ladder \(P(n)\) and we can climb to the next ladder \(P(n + 1)\), it means that we can climb to any other ladder \(P(k)\) for \(k > 0\).

This is actually a structural induction on the structure of natural number as first proposed by Peano. It states the following.

  • \(0\) is a natural number.
  • If \(n\) is natural number, then \(n + 1\) is a natural number.

Using our notation, we can write it as follows.

1
2
number :: 0
       :: number + 1

The recursion we had for numbers can be mapped to this structure.

1
2
3
4
5
def rec(n):
  if n == 0:     # number :: 0
    return base
  else:          # number :: number + 1
    return op(F(n), rec(n - 1))

Problem Solving with Inductive List

We have defined a list inductively, now we will illustrate how these can be used to solve problems recursively.

Counting

Counting Element

Problem Description

Given a list lst, we want to count the number of element in lst.

Task

Write the function count(lst) count and return the number of element in lst.

Assumptions

  • lst is a list of anything, potentially empty (i.e., len(lst) >= 0).

Restrictions

  • You are NOT allowed to convert to other data types.
  • You must solve this recursively (i.e., count must be recursive).

Since we already have the structure for inductive list, we can shortcut many of the design. We will simply first write down the inductive definition of list and add comment on what should be the count of each case.

1
2
list :: []              # count is 0
     :: [item] ++ list  # count is 1 + count of list

Since we know that the case of empty list can be checked using len(lst) == 0, we can now write the solution as follows. Note that we obtain the smaller list via lst[1:] as before.

Counting

1
2
3
4
5
def count(lst):
  if len(lst) == 0:
    return 0
  else:
    return 1 + count(lst[1:])

Multiply by n

This is the same problem from before. Again, we make the same design.

1
2
list :: []              # nothing to multiply, return []
     :: [item] ++ list  # return [item * n] ++ map of list

Here, we can retrieve the item by lst[0].

Multiply by n

1
2
3
4
5
6
def map_n(lst, n):
  if len(lst) == 0:
    return []
  else:
    return [lst[0] * n] + map_n(lst[1:], n)
    # n is unchanged during recursion

Keep Multiple of n

This is the same problem from before. Again, we make the same design.

1
2
list :: []              # nothing to keep, return []
     :: [item] ++ list  # keep [item] if multiple, else [], then append to recursion on list

Our initial solution will follow the inductive structure above.

Keep Multiple of n

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def filter_n(lst, n):
  if len(lst) == 0:
    return []
  else:
    # actual filtering
    if lst[0] % n == 0:
      item = [lst[0]]
    else:
      item = []
    return item + filter_n(lst[1:], n)

Now, the code is quite nested. So we do a little bit of thinking and we do an analysis on the conditions. We then can somewhat simplify it as follows.

Keep Multiple of n

1
2
3
4
5
6
7
def filter_n(lst, n):
  if len(lst) == 0:
    return []
  elif lst[0] % n == 0:
    return [lst[0]] + filter_n(lst[1:], n)
  else:
    return []       + filter_n(lst[1:], n)

Analysis of Solution

Let us look in more details at the aggregate of the solutions. We will see that it follows similar structure. While we can give name to this structure, it is not general because it depends on the inductive definition of the data. So what we need to do is to think of the data in terms of a self-similar structure as itself.

If we look at the operations that we are doing with the list, we will notice that we are only using certain operations. We ignore the operations on the element of the list (e.g., lst[0] % n).

  • Finding the number of element (e.g., len(lst)).
  • Indexing (e.g., lst[0]).
  • Slicing (e.g., lst[1:]).
  • Concatenation (e.g., [lst[0]] + filter_n(...)).
  • Base construction (e.g., []).

What this means is that the functions we have written above can actually work for any sequence that supports all of the operation above. Due to concatenation, we may not be able to work with range. But besides that, we can actually work with str and tuple. In fact, it works out of the box and we can even provide such sequence as input.

1
2
3
4
5
def map_n(lst, n):
  if len(lst) == 0:
    return []
  else:
    return [lst[0] * n] + map_n(lst[1:], n)

1
2
3
4
>>> map("ABCD", 2)
['AA', 'BB', 'CC', 'DD']
>>> map(("CS", 1010, "S"), 2)
['CSCS', 2020, 'SS']

The return type is still a list, but at least our input is more general. This kind of generalization will be our basis of discussing the two built-in functions to work with sequence more easily.