higher-order function

<functional programming>

(HOF) A function that can take one or more functions as arguments and/or return a function as its value.

E.g. map in (map f l) which returns the list of results of applying function f to each of the elements of list l.

A curried function is an example of a higher-order function.

Last updated: 2018-05-25

higher-order macro

<functional programming>

A means of expressing certain higher-order functions in a first-order language, proposed by Phil Wadler. Higher-order macros cannot be recursive at the top level but they may contain recursive definitions. For example, the normal, definition of the map function,

 map f []     = []
 map f (x:xs) = f x : map f xs

is higher-order because its argument, f, is a function. The alternative formulation

 map f l = map_f l
 	  map_f []     = []
 	  map_f (x:xs) = f x : m xs

defines a first-order function, map_f, that is a specialisation of map in its first argument. This can be considered a macro because it works purely by textual substitution, requiring no knowledge about f for its validity.

This is an example of partial evaluation - the call, map f l, has been partially evaluated to yeild an intermediate result. This may be useful in optimising compilation or execution, e.g. if the call to f can be subject to in-lining or when executing map_f on a long list.

Last updated: 2018-05-25

Nearby terms:

Higher Education National Software Archivehigher-order functionhigher-order macro

Try this search on Wikipedia, Wiktionary, Google, OneLook.