What string operations are basic

Question

What string operations are basic in the sense that the other string operations can be represented in terms of them? Here is a list of string operations off the top of my head (not necessarily a complete list, and your addition is welcome):

• reversal of a string
• concatenation of two strings
• repetition of a string a finite number of times
• search/match a string inside another string
• match and replace a string with another string inside a string
• split a string, at some specified positions, or according to matching result of another string
• taking a substring out of a string, according to specified positions (including taking prefix, or suffix), or according to matching result of another string
• ...

Answer 1

There are many "complete bases" for operations on strings. One is based on the representation $$ \Sigma^* = \epsilon + \Sigma \Sigma^*. $$ In words, a string is either empty or is composed of a character and a string. In order to use this representation, we need the following functions:

• nil – the empty string
• cons(x,s) – the string consisting of the character x followed by the string s
• null(s) – true if s is empty
• car(s) – returns the first character of a non-empty string
• cdr(s) – returns the string resulting from removing the first character of a non-empty string

The terminology is from Lisp; cdr is read could-er or cudder.

Another basis considers strings as arrays. There is a standard basis for reading strings:

• len(s) – the length of s
• s[i] – the character at position i

For writing strings there are several options. In the immutable case, one choice is:

• "" – the empty string
• str(x) – the string consisting of the character x
• cat(s1,s2) – the string resulting from concatenating s1 and s2

If strings are allowed to be mutable, we can add an operation s[i] = x, changing the character at position i to be x.

One can think of many other bases. Some will be more efficient than others. It all depends on what exactly you are trying to capture, what your goal is.