A lot of what I’m trying to do with mathematical models of computer systems involves operations on finite sequences.
Define a “finite sequence of length n>0” to be any total map f: {1 … n} → X for some set X. The 0-length sequence is the null map “nulls”. If f is a finite sequence of length n, then g = f affix c is the map g: {1 … n+1} → X ∪ {c} so that g(i)= f(i) for i ≤ n and g(n+1) = c. Also, if g is length n>0 then there is an f of length n-1 and some c so that g = f affix c .
A primitive recursive function on finite sequences is given by the rules F(nulls) = k and F( f affix c) = G(c,F(f)).
For example we can define prefix by (c prefix nulls) = (nulls affix c) and ( c prefix (f affix d)) = (c prefix f) affix d.
I use affix instead of append because prepend is ugly.
Two observations about common usage in computer science that differs from standard mathematical practice. First, note how I’m defining sequences as maps but being imprecise about the function images, about the set X. In CS we really only have one type of object – a sequence of binary digits- so X is always a set of finite sequences of binary digits. This is a fundamental property of computing. So if I wanted to be pedantic, I’d first define the set B of finite sequences of binary digits as the set of all maps g:{1 … n} → {0,1} plus the null map, and then define general finite sequences as maps {1 … n} → B. But we use those binary sequences as representations of other mathematical objects and even objects that are usually not considered mathematical objects such as MPEG encodings of video. So it’s convenient to speak of a sequence of integers or strings or a sequence of assorted objects without making the translation between representation and denotation (connotation? ). The second observation is that, for the same reason, second order functions are not unusual in computer science – e.g. defining prefix as a function that operates on sequences which are also functions. Note however that in non CS applied math, second order functions are also common.
Painting is The Mathematician by Diego Rivera.