Higher Order Function

aka HOF.

A function that takes a function as an argument, or returns a function as a result; this latter use is just as important as functions-which-take-functional-arguments such as "foreach" or "filter" or "reduce". The latter requires insightful cleverness in languages such as CeePlusPlus [c.f., BoostBind which relies on using functional programming concepts as a by-product of C++'s templates]. [See also FunctoidsInCpp.]

It is just a LayerOfIndirection for function references.

You may be thinking of LexicalClosures, top, but never mind. Function pointers are not an adequate substitute, otherwise CeeLanguage would be a FunctionalProgrammingLanguage.

I've always thought that qsort and the like (in C/C++) which uses pointers to functions as arguments were higher order functions. Nope. See the next line as a better example of HOFs.

How, in C++, can one define a function f that takes an integer n and returns a function g that takes an integer x and returns x+n?

Something like?:

  std::binder1st<std::plus<int> > f(int n) {
    return std::bind1st(std::plus<int>(), n);
  }

This is standard C++, though some people regard it as ugly. Not so much the use of 'std::', but the code itself, especially the syntactically significant white space between the nested >'s. That is why some people prefer languages with true first class functions.

FunctoidsInCpp discusses FC++ which is a library implementing this and much more. -- JohnFletcher

Some languages have built-in convenience mechanisms to do this. There are some examples in everyone's favorite languages below, as well as on the CommonHigherOrderFunctions page.

It is rather simple to accomplish this in the PythonLanguage:

def f(n):
    def g(x):
        return x + n
    return g

BlocksInRuby lists some great usages of higher order functions. In Ruby, they're called "blocks", they are a special language construct, and you cannot pass more than one to any routine.

Incorrect, blocks are anonymous functions, not higher order functions. The higher order functions would be the function to which you pass the block. The combination of anonymous functions and higher order functions together are where you get the power from, the anonymous functions essentially specialize the higher order function. Any language that supports passing functions as parameters can support higher order functions, but without anonymous functions, they won't get used too often, CsharpLanguage is such a beast. -- RamonLeon

[Although not for much longer - version 2 of the language will feature anonymous functions (which are fully-fledged LexicalClosures), along with a standard set of HigherOrderFunction-style methods on the collection classes (usual map/filter/forall/iter/etc, but with different names (presumably they don't want to "confuse" people who haven't seen them before... at the expense of confusing those of us who have seen them before...)). See http://blogs.msdn.com/kcwalina/archive/2004/06/22/162533.aspx for some preliminary details of the collection methods. -- MikeRoome]

Not suprising, it is standard Microsoft practice to rename and reimplement and then pretend they invented something new. They'll be nice to have though. -- rl

No, it's standard Microsoft practice to take something, rename it, patent it and pretend they invented something new.

No, it's everyone else's practice to say "look at all these languages with feature x - isn't it great that we all build on each other like that?" unless someone at Microsoft does exactly the same thing.

(But you didn't grasp the anti-Microsoft complain. Patenting means to take control and to stop everyone else to "build on that" without consent, so the "great we build on each other" will become "look, they have built on Microsoft's", plus "let's see if we can sue them" when applicable... Microsoft does not want you to say "we all build on each other", but "we all build on Microsoft's great original ideas", though they have just build on the other. See the difference? Of course, it does not happen to be always like this, but the complain is about this MS general attitude, which tears MS away from a community behaviour where you, like everyone else, can say happily "great that we build on each other")

Sure. I program in CommonLisp. Using HigherOrderFunctions is so common that you don't even notice it. The built-in ones are: mapcar (and friends), apply, funcall, sort (it takes the comparison function object as argument), count-if, remove-if, delete-if, and a whole heap of functions which take the :test optional key argument (e.g. find).

The way you use these is in expressions like

(dolist (func (find-all-if #'suitable-p *my-objs-containing-a-func))
(funcall (object-function-slot func)))

Without dolist it looks much better. ;-)

(mapc #'funcall (find-all-if #'suitable-p *my-objs-containing-a-func))

But, as I say, that's just the built-ins. The real power comes from using this naturally in your own algorithms. For example, the StrategyPattern totally disappears in such a language: you just pass the function to use instead of creating classes for the strategy.

(As a side note, many, if not most, of the patterns in the patterns book are unnecessary or considerably simpler in languages which support functions as first class objects. See PeterNorvig's DesignPatternsInDynamicProgramming.

-- AlainPicard (but feel free to RefactorMe)

This isn't much better than the CeePlusPlus version of a HigherOrderFunction. They're both ugly, and which is less ugly just depends on which you're more used to looking at.

Here are three simple examples of InternalIterators (using the MapFunction).

PerlLanguage example:

sub double
{
return 2 * shift;
}

@a = ( 1, 2, 3, 4, 5 );
@b = map { double( $_ ) } @a;

... or perl's "list-comprehension-ish" 'gather' clause

use Perl6::Gather;
@b = gather { take $_ * 2 } foreach 1..5;

RubyLanguage example:

def double ( num )
return 2 * num
end

a = [ 1, 2, 3, 4, 5 ]
b = a.collect { |value| double( value ) }

Alternative Ruby version(s):

double = lambda { |num| 2 * num }
b = a.map(&double)

or even

b = a.map { |num| 2 * num }

SmalltalkLanguage example: (very similar to the RubyLanguage example)

Number>>double
^ 2 * self

a := #(1 2 3 4 5).
b := a collect: [ :value | value double].

(1 to: 5) collect: [ :i | 2 * i ]

PythonLanguage example:

... with explicit function declaration

def doubleit( num ):
return 2*num
a = ( 1, 2, 3, 4, 5 )
b = map( doubleit, a )

... or with lambda

b = map(lambda num: 2 * num, a)

... or with ListComprehension:

b = [ 2 * num for num in a ]

SchemeLanguage example:

(define (double num) (* 2 num))
(define a '(1 2 3 4 5))
(define b (map double a))

(define b (map (lambda (x) (* 2 x)) a))

CommonLisp example:

(defun double (num) (* 2 num))
(defvar *a* (list 1 2 3 4 5))
(defvar *b* (mapcar #'double *a*))

(defvar *b* (mapcar #'(lambda (x) (* 2 x)) *a*)

ObjectiveCaml example:

let b = 
  let a = [1;2;3;4;5] in List.map (( * ) 2) a;;

HaskellLanguage example:

b = map (*2) [1..5]

In all cases, array b equals [ 2, 4, 6, 8, 10 ].

ErlangLanguage example:

... with higher-order map and a LambdaExpression

lists:map(fun(X) -> 2*X end, lists:seq(1,5)).

... or with a ListComprehension:

[ 2*X || X <- lists:seq(1,5) ].

CeePlusPlus example:

vector<double> a, b;
// set a values to whatever
transform (
a.begin(), a.end(),// take this range
back_inserter(b),// append to b
bind1st(multiplies<double>(), 2)); // after multiplying by 2.

or with boost::lambda (BoostLambdaLibrary):

transform (a.begin(), a.end(), back_inserter(b), _1 * 2);

You can use a template function that uses one or more of its arguments as a FunctorObject in CeePlusPlus to make a Higher Order Function.

GroovyLanguage example: (basically the same as RubyLanguage and SmalltalkLanguage)

a = [1,2,3,4,5]
b = a.collect { 2 * it}

CsharpLanguage v2 example:

 int[] a = { 1, 2, 3, 4, 5 };
 int[] b = Array.ConvertAll(a, delegate(int x) { return 2 * x; });

or using the List collection class:

 List<int> a = new List<int>(new int[] { 1, 2, 3, 4, 5 });
 List<int> b = a.ConvertAll(delegate(int x) { return 2 * x; });

Also, JavaScript's treatment of functions as first class objects makes it very simple to write HigherOrderFunctions, to use the above example we have to write map, but it's pretty simple:

Array.prototype.map=function(aBlock){
  var result=new Array();
  for(var index=0;index<this.length;index++)
result.push(aBlock(this[index]));
  return result;
}

usage...

var a = [1,2,3,4,5];
var b = a.map(function(x){return x*2;});

var b=[1,2,3,4,5].map(function(x){return x*2});

JohnHughes's paper "WhyFunctionalProgrammingMatters" describes Higher Order Functions as functions that apply some policy to other functions in order to produce new functions. Functions are composed in this way to produce anonymous functions that do the work of the program. So, in order to use a Higher Order Function you would pass another function as a parameter. A couple of examples given of Higher Order Functions are reduce, which applies a function to every element of a collection and some running total which is then replaced by the output of the function, and map, which creates a new collection by applying some function to every element in a collection and adding the result to a new collection. -- PhilGoodwin

Ocaml's (ObjectiveCaml) MySql-bindings provide nice practical examples of usage of higher order functions: it contains a routine iter, which takes a query result, a function that operates on an array of values of fields, and evaluates the function for every row that was returned in the result. Another routine is opt f v, which is meant to be used with values that might be null; for non-null values, it returns f applied to v, for null values, it returns null. So you don't have to write null handling into the function f itself.

Is an ordinary function (one which neither takes a function as an argument, nor returns one as a result) a 0th order function, or a 1st order function? (Or do we even care?)

Also, is it ever useful to distinguish between different orders of functions? (Say, a second order function is one which either accepts or returns a first-order function, but no higher; a third-order function can accept or return a second-order function, etc.)

Not that I'm an authority, but I think it'd just be a regular function or a higher order function. Higher order isn't meant to be a numerical designation, but a way to describe functions that are specialized by, or produce other functions.

PhpLanguage example:

function double($number)
{
return $number * 2;
}

$array = array(1,2,3,4,5);
$result = array_map("double", $array); // perhaps using the array_map function is cheating? ;)

PhpLanguage has a few interesting built-in functions to deal with higher-order functions. is_callable() will tell you if the given var is in fact a string containing a callable function name, an array containing an object and method name, or an array containing the class name and method name (for static methods). You can also quite easily use the contents of a variable to call a function....

$foo = "myFunkyFunc";
$foo($arg, $arg1); // Calls myFunkyFunk.

Although it works, I prefer to use the following method, as it is a little more readable

$foo = "myFunkyFunc";
call_user_func($foo, $arg, $arg1);

So, php has () as a postfix EvilEval?

PHP has variable variable names and variable function names. I believe it is called reflection in OO terms. So, for example, you can say

$foo = "myVar";
$x = $$foo;     // $x contains the same value as $myVar;

Getting PHP to return functions is somewhat more problematic. There is the "create_function()" function, to which you pass the parameter list and source of the function body, but its return value is pretty much unusable for creating further functions without a lot of grief (it contains a NUL character that really messes things about when you try and embed it in the source code of a new function). Even a function to implement function composition is problematic.

Not since PHP 5.3, which provides syntax for first-order functions (as another type of "callable" thing). As a side effect of the implementation, one can also write objects with a method that is called when the object is called as a function (i.e., as $obj('foo')).

$array = [1,2,3,4,5];
$result = array_map(function($number)
{
return $number * 2;
}, $array);

A function to implement function composition would be

function o($f, $g)
{
// Variables in the outer scope have to be imported explicitly
return function($x)use($f, $g)
{
return $f($g($x));
};
}

Of course, for proper generality you'd want o() to be curried:

function o($f)
{
return function($g)use($f)
{
return function($x)use($f, $g)
{
return $f($g($x));
};
};
}

Skeptical view of HOF's: DynamicStringsVsFunctional, ArrayDeletionExample

This was moved from ArrayDeletionExample

To clarify it for me, does the HigherOrderFunction enable the second example?

Less than HigherOrderFunction (First example)

 Keys = Select.Data(Entity.Name)
 Loop
Key = Remove.Field(Keys); * Removes Key from Keys
 Until Key = EOF

* Code for each key

 Repeat

HigherOrderFunction (Second example)

 Keys = Create.Array.Iterator(Select.Data(Entity.Name))
 Iterate(Keys, Get.Object.Code("** Code for each key"))

And I notice this becomes a one-liner

 Iterate(Create.Array.Iterator(Select.Data(Entity.Name)), Get.Object.Code("** Code for each key"))

-- PeterLynch

That is a rather long "line". I find code easier to read if parts are divided on multiple lines.

I think C programmers prefer this version -

It(CAI(SD(E)), GOC("** Code for each key"))

But I prefer the first version. Because it lays out the logic clearly. The admittedly smaller versions hide the fact that there is a loop, and scanning the code, I could easily miss the significance of that. -- PeterLynch

As I read further about FunctionalProgramming, I think I get the difference between HigherOrderFunctions and ProceduralFunction?s. While many languages provide an eval-like facility, those that are HigherOrder? parse and interpret scope at compile time - your 'generated' code is parsed at compile time. Other languages compile the 'generated' code at run-time, like an interpreter.

So the above -

 Iterate(Create.Array.Iterator(Select.Data(Entity.Name)), Get.Object.Code("** Code for each key"))

Would read -

 Iterate(Create.Array.Iterator(Select.Data(Entity.Name)), -
 {Code.Compiler.Directive}"** Code for each key"{/Code.Compiler.Directive})

(where the Code.Compile.Directive is whatever language specific syntax is used to indicate code.)

Is this correct? -- PeterLynch

See also: CurryingSchonfinkelling (now why didn't I guess from the name that's what it was about?), EvalVsPolymorphism, SwitchCaseListVersusHof

CategoryFunctionalProgramming CategoryInManyProgrammingLanguages