High Order Functions

(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.

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]


(Just pseudo-code is fine)

  1. Write down your definition for filter, map
  2. 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)
comments powered by Disqus