# Functional Forms of Repetition, Loop, Iteration

By Xah Lee. Date: .
xtodo

## Functional Forms of Repetition, Loop, Iteration

now, i feel like typing, so let me give a monolog thesis.

on the forms of loop in functional programing, what makes them differ, and if there are other forms.

so, in functional programing, you have 3 main types of repetition (aka loop/iteration). they are: map, recursion, fold (aka reduce)

• map is familiar to most. it applies a function to a lisp of values.
• recursion is familiar to functional programers. it is a function that calls itself.
• reduce is also common today, in python and JavaScript. the function goes thru a list of values, like a loop, but produce one single end value. (in contrast to map)

now, there seems to be many complexities if you use reduce or recursion. often, you need to change your function, its input and output, so that it passes on the state.

this, the need to change your functions, to do a loop, is annoying. so lets look at why it occur.

in “imperative programing”, eg c cpp java python, to do a loop, you simply write statements or commands in the body of the loop, to compute what you want, and also expression the condition of when to stop.

in functional programing forms of loop, you cannot do that. because function forms a closed independent semantic unit, the condition check, now must be part of your function, and in a clean way in the form of input output.

and this is why, you run into conceptual complexities. now you need to make your function clean.

when you map a function f to a list of values, that function's purpose is clean. but when you need to make the function call itself, or do a reduce, with a condition when to stop, you have to embed this conditional state into the function. this, is the cause of the complexity.

in other words, you have to rewrite the function f, to do something more than what it originally is meant to do.

so, now we are thinking, why are we doing functional programing again, if function forms of loop creates fair bit of complexity?

Obvious, the gist of functional programing is that function forms an algorithmic unit, independent of other parts of the program. This, is, the advantage of functional programing. It allows you to be able to move a function code anywhere. Also, the program is much easier to analyze.

so, the added complexity of doing a loop (happens often), is the cost. A disadvantage of functional programing.

now, back to about functional forms of loop.

• in functional forms of loop, map, recurse, reduce, what makes them differ?
• why do we say they are different “forms”?
• what is the essence, that makes them different?
• and, is it possible, to have other, forms of loop?

basically, all these, is about the need to “repeat” a computation, with different data during the repetition. This is the essence.

we have the general different forms of map, recurse, reduce, is due to, different types of loop. namely, do you want the repetition to take a different value each time, or merge with previous value, or previous n values, or do you want it to stop once a condition is met.

It is not necessary, to have all these different forms. A recursive function can do them all. And we can also convert any of the loop forms to the other.

For example, to convert a “reduce” form of f to recursion, one can just change f so that f now takes 2 args, num and a list, and call itself, each time feeding the list with one less item. until the list is empty.

to convert a “map” to recursion, you do the same, except the function now adds a third arg of empty list, and each time add a item, until this new list is same length as input list.

here's another example of a functional form of loop, called MapThread in WolframLang, the concept is a kinda parallel map. suppose you have a function of 2 args f(a,b), and you have 2 lists {a,b,c} and {x,y,z}

you want to get

{f(a,x),f(b,y),f(c,z)}.

in WolframLang, you do MapThread[f, {list1,list2}]. in Common Lisp and others, you simply use mapcar

this is interesting, because it's another form of loop, like map, but now works with multiple lists.

another example is MapIndexed, where you need to map a function to a list but your function also need the index.

these variations of map is shown, to illustrate, they are all forms of functional loop.

another interesting form is WolframLang FoldWhile. It is like python JavaScript reduce, but with a condition to stop.

we are looking at the various forms of functional loop, to look into how they differ, why they differ, why do we need this different forms.

and again, we find that, they are a matter of convenience.