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 Cee Plus Plus [c.f., Boost Bind which relies on using functional programming concepts as a by-product of C++'s templates]. [See also Functoids In Cpp.]
It is just a Layer Of Indirection for function references.
You may be thinking of Lexical Closures, top, but never mind. Function pointers are not an adequate substitute, otherwise Cee Language would be a Functional Programming Language.
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.
Functoids In Cpp discusses FC++ which is a library implementing this and much more. -- John Fletcher
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 Common Higher Order Functions page.
It is rather simple to accomplish this in the Python Language:
def f(n): def g(x): return x + n return g
Blocks In Ruby 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, Csharp Language is such a beast. -- Ramon Leon
[Although not for much longer - version 2 of the language will feature anonymous functions (which are fully-fledged Lexical Closures), along with a standard set of Higher Order Function-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 blogs.msdn.com 
for some preliminary details of the collection methods. -- Mike Roome]
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 Common Lisp. Using Higher Order Functions 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 Strategy Pattern 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 Peter Norvig's Design Patterns In Dynamic Programming.
-- Alain Picard (but feel free to Refactor Me)
This isn't much better than the Cee Plus Plus version of a Higher Order Function. 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 Internal Iterators (using the Map Function).
Perl Language 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;
Ruby Language 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 }
Smalltalk Language example: (very similar to the Ruby Language example)
Number>>double ^ 2 * self
a := #(1 2 3 4 5). b := a collect: [ :value | value double].
or
(1 to:
5) collect: [ :i | 2 * i ]
Python Language 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 ]
Scheme Language example:
(define (double num) (* 2 num)) (define a '(1 2 3 4 5)) (define b (map double a))
or
(define b (map (lambda (x) (* 2 x)) a))
Common Lisp example:
(defun double (num) (* 2 num)) (defvar *a* (list 1 2 3 4 5)) (defvar *b* (mapcar #'double *a*))
or
(defvar *b* (mapcar #'(lambda (x) (* 2 x)) *a*)
Objective Caml example:
let b = let a = [1;2;3;4;5] in List.map (( * ) 2) a;;
Haskell Language example:
b = map (*2) [1..5]
In all cases, array b equals [ 2, 4, 6, 8, 10 ].
Erlang Language 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) ].
Cee Plus Plus 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 (Boost Lambda Library):
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 Functor Object in Cee Plus Plus to make a Higher Order Function.
Groovy Language example: (basically the same as Ruby Language and Smalltalk Language)
a = [1,2,3,4,5] b = a.collect { 2 * it}
Csharp Language v2 example:
int[] a = { 1, 2, 3, 4, 5 }; int[] b = Array.Convert''''''All(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.Convert''''''All(delegate(int x) { return 2 * x; });
Also, Java Script's treatment of functions as first class objects makes it very simple to write Higher Order Functions, 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;});
or
var b=[1,2,3,4,5].map(function(x){return x*2});
John Hughes's paper "Why Functional Programming Matters" 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. -- Phil Goodwin
Ocaml's (Objective Caml) My Sql-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.
Php Language 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? ;)
Php Language 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 Evil Eval
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: Dynamic Strings Vs Functional, Array Deletion Example
This was moved from Array Deletion Example
To clarify it for me, does the Higher Order Function enable the second example?
Less than Higher Order Function (First example)
Keys = Select.Data(Entity.Name) Loop Key = Remove.Field(Keys); * Removes Key from Keys Until Key = EOF
Code for each key
Repeat
Higher Order Function (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"))
-- Peter Lynch
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. -- Peter Lynch
As I read further about Functional Programming, I think I get the difference between Higher Order Functions and Procedural Functions. While many languages provide an eval-like facility, those that are Higher Order 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? -- Peter Lynch
See also: Currying Schonfinkelling (now why didn't I guess from the name that's what it was about?), Eval Vs Polymorphism, Switch Case List Versus Hof
See original on c2.com