5
$\begingroup$

filter() in functional programming can be thought of as being analogous to an equation that filters the range of the variable.

map() can be through of as a function mapping domain to codomain.

reduce() is the only one I have a problem with. To me it just seems to be a special instance of map / function, where $R^{n} \rightarrow R^{1}$.

Is there a unique general mathematical concept / object associated with reduce()?

$\endgroup$
1
  • $\begingroup$ reduce is a catamorphism. both map and filter can be expressed in terms of reduce BTW. $\endgroup$
    – Will Ness
    Jan 9, 2018 at 9:11

1 Answer 1

1
$\begingroup$

Map applies a unary function to each element in the sequence and returns a new sequence containing the results, in the same order

$$\mathrm{map}\colon (E\to F) \times \mathrm{Seq}\langle E\rangle \rightarrow \mathrm{Seq}\langle F\rangle\,.$$

Filter tests each element with a unary predicate. Elements that satisfy the predicate are kept; those that don’t are removed.

$$\mathrm{filter}\colon (E \rightarrow \mathrm{boolean}) \times \mathrm{Seq}\langle E\rangle \rightarrow \mathrm{Seq}\langle E\rangle\,.$$

Reduce combines the elements of the sequence together, using a binary function. In addition to the function and the list, it also takes an initial value that initializes the reduction, and that ends up being the return value if the list is empty.

$$\mathrm{reduce}\colon (F \times E \rightarrow F) \times \mathrm{Seq}\langle E\rangle \times F \rightarrow F\,.$$

Example:

\begin{align*} \mathrm{result}_0 &= \mathrm{init} \\ \mathrm{result}_1 &= f(\mathrm{result}_0, \mathrm{list}[0]) \\ \mathrm{result}_2 &= f(\mathrm{result}_1, \mathrm{list}[1]) \\ &\ \ \vdots\\ \mathrm{result}_n &= f(\mathrm{result}_{n-1}, \mathrm{list}[n-1]) \end{align*}

Hence you can see it as a function $\mathbb{R}^n \rightarrow \mathbb{R}$

Source: http://web.mit.edu/6.005/www/fa15/classes/25-map-filter-reduce/

$\endgroup$
2
  • $\begingroup$ You write down the signatures of the FP idioms using mathematical notation. That's not wrong, but is it helpful? Clearly, these functions can be defined but they are not idiomatic in mathematics by any means. $\endgroup$
    – Raphael
    Sep 1, 2017 at 10:33
  • 3
    $\begingroup$ All three of these are examples of list algebra homomorphism. Answering this way would also characterise the property they have to satisfy. I'll write one if I got time. $\endgroup$ Sep 2, 2017 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.