# Right notation to recurse over a sequence or list

I have a function $f(x, a)$ which is invoked over all the elements of a sequence feeding the result to the next call, with $x$ being the next element in the list and $a$ the accumulated result. What is the correct (and popular) notation to write this properly?

Lets say $F(p, a)$ is the recursive function which takes the sequence, $p$, and runs $f(x, a)$ on each element of $p$.

I was thinking of defining it something like this:

$F(p, a) = \begin{cases} a & \text{if } p = \langle \rangle\\ f(F(\langle x_1, ..., x_{n-1} \rangle, a), x_n) & \text{if } p = \langle x_1, ..., x_n \rangle \end{cases}$

But for some reason it seems incorrect for the case when $p$ has just one element. Is there a better way to define it? Maybe some way of denoting the head and tail of the list?

You have the concept of folding. Your definition seem to be right for me. It's the right fold. Note, that there is also left folding:

$$F(p,a) = \begin{cases} a & ; p=[] \\ F([x_1,\ldots,x_{n-1}], f(x_n, a)) & ; p = [x_1, \ldots, x_n]; n \ge 1 \end{cases}$$

EDIT: You can also define it with the colon operator (which is the concatenation of an element to a list):

$$F(p,a) = \begin{cases} a & ; p=[] \\ F(xs, f(x, a)) & ; p = x : xs \end{cases}$$

That's the way it is usually done in haskell...

• Thanks. My concern is that if $n = 1$ then $x_1, ..., x_{n-1}$ becomes invalid, because $n-1$ becomes $0$, so $x_1, ..., x_0$ is incorrect, when it should be the empty sequence. I once saw somewhere a different syntax, but I cannot recall where, but it was something like $F(p, h:t) = F(t, f(h, a))$ but I am not sure if it was with the colon and whether it is correct. – jbx May 10 '15 at 22:05
• Regarding the right fold (vs left fold), the result would be different though right? I want to first apply $f()$ to $x_1$, then $x_2$ etc. while with the left fold it applies $f()$ to $x_n$ first. – jbx May 10 '15 at 22:08
• @jbx: depending on $f$ from the right and left fold you might get different results... the colon is the concatenation of an element to a list... – Stephan Kulla May 11 '15 at 8:36
• Thanks. Yes I was looking for something like that, but I wasn't sure if the colon was accepted mathematical notation for the head / tail of a list. (In Haskell its written :, in Scala its written ::). To me it seems a bit more correct, because $xs$ can be the empty list. – jbx May 11 '15 at 14:59