*(This is a post for CS320 Boston University.)*

Recall that in functional programming languages, functions are first class citizens. They are values, and can be passed on to other functions as arguments.

**High-order functions** are those functions that take function values as arguments, or return function values as output. *[wiki]*

There are some well-defined names in the world of high-order functions. *[ref]*

`fold: (list, f, init) -> value`

: it takes a list, a binary function, an initial value, and returns a single value that is the result of putting that binary operation in between elements. It is used to reduce/simplify/transform a data value (not limited to lists). e.g.`fold (1::2::3::4::nil, add, 0)`

can be seen as`add (4, add (3, add (2, add (1, 0))))`

. Or you can think of it this way: replacing the constructor with your own binary function. The list is originally`cons (4, cons (3, cons (2, cons (1, nil))))`

.`filter: (list, pred) -> list`

: it takes a list, and a predicate function (a function that takes an element and return a boolean according to its logic), and return a list that contains only elements that satisfies the predicate. It is used to remove or select only some componenets of a data value (not limited to lists).`map: (list, trans) -> list`

: it takes a list, and a mapping function, and return a mapped list by applying the mapping function on every single element of the original list. It is used to modify all the components of a data value using a single, often local transformation that is applied to all the components across the entire data value.

Actually, the `fold`

operation is of great importance. It's not just a function, it can be seen as a whole class of functions that reduce something into something else. A lot other functions can be implemented using `fold`

.

```
//pseudo-code
maximum (xs) => fold (xs, max, neg_infinity)
sum (xs) => fold (xs, add, 0)
height (tree) => fold (tree, lam cs => 1 + maximum (cs), 0)
```

We've already seen the definition of `fold`

in class [link]. These high-order functions let us solve problems at high level - we care only about the solution, not the execution order of these solutions. Using a composition of `fold`

/`map`

/`filter`

to describe a solution imposes less restrictions on how that computation can be done, compared to a sequential list of operations in a imperative language. *[ref]*

### Execrises

*(Just pseudo-code is fine)*

- Write down your definition for
`filter`

,`map`

- Write down your definition for
`filter`

and`map`

using`fold`

. (Hint, you can define anonymous functions/lambda expressions like`lam (x, y) => x + y`

.

A possible solution in ATS.

```
datatype list (a:t@ype) =
| cons of (a, list (a))
| nil of ()
extern fun {a,b:t@ype} fold (list (a), (a, b) -> b, b): b
extern fun {a:t@ype} filter (list (a), a -> bool): list (a)
extern fun {a,b:t@ype} map (list (a), a -> b): list (b)
implement {a,b} fold (xs, f, init) =
case+ xs of
| nil _ => init
| cons (x, xs) => f (x, fold (xs, f, init))
#define :: cons
implement {a} filter (xs, f) =
fold<a, list(a)> (xs, lam (x, ys) => if f(x) then x::ys else ys, nil)
implement map {a,b} (xs, f) =
fold<a, list(a)> (xs, lam (x, ys) => f(x)::ys, nil)
```