joint work with Laure Daviaud and Krishna S

We define a class of functions, called 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: first-order list functions are constructed by starting with some basic functions (e.g.~projections, or head and tail operations on lists) and putting them together using four combinators (most importantly, composition of functions). We show that first-order list functions  are exactly the same as first-order transductions, under a suitable encoding of the inputs. Finally, we observe that first-order list functions can be efficiently evaluated (linear time, also AC0), and their equivalence problem is decidable.