The theory of Lists and $\Sigma$-definability

We consider two-sorted structures (lists algebras) consisting of a basic set $S$ and a set of lists $I_S$ (lists are ordered collections of elements from $S \cup I_S$) with natural relations and operations such as membership relation, head and tail operations etc. and show that recursively definable functions are $\Sigma$-definable in the lists algebras. The recursion is on the length and depth of a list.