Looping Constructs in Functional Programing. What and Why Map Fold Some Every?

By Xah Lee. Date: . Last updated: .

Functional Programing Forms of Loop, Logical Synthesis of the Different Functions Such as Map, Fold, Every, Etc.

Here we detail why and how of the many functions in functional programing languages, such as map filter some every reduce etc.

they are effectively convenient forms of writing a loop.

Recursive Function

In functional programing, the fundamental form of loop, is defining a function that calls itself (aka recursive function). You don't write a loop because that means you need to update a variable to keep a state. e.g. for (let i = 0; i < x.length; i++) {body} But functional programing style means not to mutate a variable.

(“recursive function” came from theoretical computer science and math. i.e. lambda calculus, church numerals, Recursion Theory aka Computability Theory.)

recursive function is the most general form of doing loop in functional programing.

in functional programing languages, some convenient functions are added to make it easier to do loop, without needing to define recursive function.

Map

map is the most common. It lets f go thru a list, without needing to write a recursive function. 

// implement a recursive function to add 1 to a list

/*
fmapAdd1ToArray(xlist)
add 1 to each element in array xlist.
*/
const fmapAdd1ToArray = (xlist, xstate = []) => {
 if (xlist.length === 0) {
  return xstate;
 } else {
  xstate.push(((x) => x + 1)(xlist.shift()));
  return fmapAdd1ToArray(xlist, xstate);
 }
};

console.log(fmapAdd1ToArray([1, 2, 3, 4, 5]));
// [ 2, 3, 4, 5, 6 ]

but with map, you can call map(f , list) for any function f. Much simpler.

Fold (aka reduce)

Then there is reduce (aka fold). It captures the gist of a loop. Namely, a recursive function passes a state to itself, and each time with an optional external input. You can use reduce to implement map, and all other recursive functions.

reduce is the second most general form of loop, second to defining a recursive function. 

// implement reduce (fold)

/*
ffold(xfun, xstate, xlist)
apply function xfun to each element in array xlist.
xstate should be empty array.
*/
const ffold = (xfun, xstate, xlist) => {
 if (xlist.length === 0) {
  return xstate;
 } else {
  xstate.push(xfun(xlist.shift()));
  return ffold(xfun, xstate, xlist);
 }
};

console.log([1, 2, 3, 4, 5].map((x) => x + 1));
// [ 2, 3, 4, 5, 6 ]

console.log(ffold((x) => x + 1, [], [1, 2, 3, 4, 5]));
// [ 2, 3, 4, 5, 6 ]

Foreach

foreach is like map, when you don't care about the return value.

Some, Every, Nest, FixedPoint

Now, some and every is a loop with break. It adds a condition to stop.

In Wolfram language, it has Nest, NestWhile, and FixedPoint. They are all similar to JavaScript some, which is a loop with a condition to stop.

Filter

Second most common after map, is filter. It allows you to remove some elements.

Map to Multiple Lists

Sometimes you need to map a function to multiple lists, the function takes multiple arguments. Each time, it takes one item from each list. This is like parallel map.

Map with Index

Sometimes you need to map a function to a list, but you also need to know the index of the element.

Max, Min, Range, Sort, Delete Duplicate, Etc.

There are lots other functions that basically do loops. These are easy to understand from their function names. For example,

xtodo

functional programing on loop