Chapter 7 Recursive Data Types160
Definition 7.1.1.LetAbe a nonempty set called analphabet, whose elements are
referred to ascharacters,letters, orsymbols. The recursive data type,A, of strings
over alphabet,A, are defined as follows:
Base case: the empty string,, is inA. Constructor case: Ifa 2 Aands 2 A, then the pairha;si 2 A.Sof0;1gare supposed to be the binary strings.
The usual way to treat binary strings is as sequences of 0’s and 1’s. For example,
we have identified the length-4 binary string 1011 as a sequence of bits, of a 4-
tuple, namely,.1;0;1;1/. But according to the recursive Definition 7.1.1, this string
would be represented by nested pairs, namely
h1;h0;h1;h1;iiii:These nested pairs are definitely cumbersome, and may also seem bizarre, but they
actually reflect the way lists of characters would be represented in programming
languages like Scheme or Python, whereha;siwould correspond to cons.a;s/.
Notice that we haven’t said exactly how the empty string is represented. It really
doesn’t matter as long as we can recognize the empty string and not confuse it with
any nonempty string.
Continuing the recursive approach, let’s define the length of a string.
Definition 7.1.2.The length,jsj, of a string,s, is defined recursively based on the
definition ofs 2 A:
Base case:jjWWD 0.
Constructor case:jha;sijWWD 1 Cjsj.
This definition of length follows a standard pattern: functions on recursive data
types can be defined recursively using the same cases as the data type definition.
Namely, to define a function,f, on a recursive data type, define the value offfor
the base cases of the data type definition, and then define the value off in each
constructor case in terms of the values offon the component data items.
Let’s do another example: theconcatenationstof the stringssandtis the
string consisting of the letters ofs followed by the letters oft. This is a per-
fectly clear mathematical definition of concatenation (except maybe for what to do
with the empty string), and in terms of Scheme/Python lists,stwould be the list
append.s;t/. Here’s a recursive definition of concatenation.