  We define two classes of functions, called regular (respectively,
first-order) list functions, which manipulate objects such as lists, lists of
lists, pairs of lists, lists of pairs of lists, etc. The definition is in the
style of regular expressions: the functions are constructed by starting with
some basic functions (e.g. projections from pairs, or head and tail operations
on lists) and putting them together using four combinators (most importantly,
composition of functions). Our main results are that first-order list functions
are exactly the same as first-order transductions, under a suitable encoding of
the inputs; and the regular list functions are exactly the same as
MSO-transductions.
