# How to write a functional fold in mathematics?

Given is a sequence of natural numbers: $1,2,...,n$. I want to choose two elements $a,b$ of this sequence, calculate $c=ab+a+b$ and write $c$ back to the sequence. After $n-1$ iterations, there is only one element left. When I choose $n=10$ this element is: $39916799$

I have written this algorithm in Haskell:

foldl (\a b -> a*b+a+b) 0 [1..10]


and in Scala:

((1 to 10) foldLeft 0) {(a,b) => a*b+a+b}


Both work fine. Now I want to define this algorithm, which uses a fold, in mathematics. I came to this:

$$f: [1,n]n\in \mathbb N \rightarrow \mathbb N$$ $$f(p)=\cases{p_0p_1+p_0+p_1, &if\ |p|=2\cr f(p_0p_1+p_0+p_1+\sum\limits_{i=2}^n i), & else}$$

I don't think this is completely correct. For example, a interval is defined on $\mathbb R$ not $\mathbb N$ thus I don't know if it is possible to narrow it on $\mathbb N$. Can someone say me if it is possible to write a fold in mathematics and if yes, how?

Notice: I know, the fold is unnecessary because the result can be calculated with $(n+1)!-1$, but I want to know how to write such a fold in mathematics.

-
The description you have in the first paragraph is already a perfectly clear mathematical description of the process. Mathematics doesn't mean writing everything in hard-to-read notation. – ShreevatsaR Nov 17 '11 at 11:22
ShreevatsaR is right. By the way, your operation is the same as $(a_1,a_2,\ldots,a_n)\mapsto (a_1+1)(a_2+1)\cdots(a_n+1)-1$. – Henning Makholm Nov 17 '11 at 12:48
@ShreevatsaR: Ok, that's a good point. But what if I want to represent the idea of fold in mathematics. Is it better to use own words, too? Or more something like QED posted in his answer? – sschaef Nov 17 '11 at 15:30
Any description that mathematicians understand is good enough. But if you really want to go formal, fold can be nicely expressed using the language of category theory. This is what Lambek's lemma is about. See, for example, here: cs.nott.ac.uk/~vxc/mgs/MGS2011_categories.pdf (You need to do a tiny bit of massaging because foldr is more natural for lists than foldl, but it's not a big deal.) – Dan Piponi Nov 17 '11 at 18:07

It is unclear what you mean by "represent the idea in mathematics", but I suspect that you're working from too high an assumption about of what mathematics requires. Except for a few very specialized fields, mathematics is not code. When you're writing mathematics, you're writing for people, and the only thing that matters is getting your point across as clearly as possible. Sometimes this calls for the use of formulas and symbolism; at other times it doesn't.

In this case, your initial informal presentation is quite understandable and therefore fine to use in an argument. The reader will, however, wonder whether it makes a difference for the result how you choose the two elements to operate on; you owe him some kind of proof that it doesn't. The most straightforward way to do this is to prove that the operation $(x,y)\mapsto xy+x+y$ is associative and commutative. With many audiences it will actually suffice just to assert that the operation is associative and commitative, leaving it to the reader to carry out the simple proofs if he doubts it. But you do have to at least assert it explicitly.

If you don't want to deal with the freedom to do the operation in different orders, you could say something like

Let $f(x,y)=xy+x+y$, and consider $q=f(f(\cdots f(f(a_1,a_2),a_3), \cdots),a_n)$.

Unless you're in a classroom setting where you're supposed to demonstrate that you know how to unfold "$\ldots$" into formally recursive definitions, this is perfectly acceptable, and much easier on the reader than the explicit recursion that you'd have to use to make yourself understood by a computer.

-

Since set theory doesn't support lambda you can write it like this:

$$\text{foldl}(f,0,(1,2,\ldots,10))$$

where

$$f(a,b) = a\cdot b+a+b$$

and

$$\begin{array}{rcl} \text{foldl}(f,k,()) &=& k \\ \text{foldl}(f,k,(x,y,\ldots,z)) &=& \text{foldl}(f,f(k,x),(y,\ldots,z)) \end{array}$$

-
Thanks, nice solution. But this is more an exact representation of fold than the "idea" of fold written in mathematics. – sschaef Nov 17 '11 at 15:32
@Antoras, I don't understand your comment – user16697 Nov 17 '11 at 15:56
@Antoras, maybe you have mixed up foldl (a strange contrived function) and foldr (a natural function which has an abstract categorization)? – user16697 Nov 17 '11 at 15:56