Higher Order Function

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.

• 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?

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

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

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.

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)))

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

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

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;

	def double ( num )
		return 2 * num
	end

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

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

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

	Number>>double
		^ 2 * self

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

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

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

	(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*)

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

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

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) ].

	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.

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

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

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

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

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

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

	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});

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 = (1,2,3,4,5)
	$result = array_map("double", $array); // perhaps using the array_map function is cheating? ;)

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

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

• This was moved from ArrayDeletionExample

• 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"))

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"))

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"))

 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

This page mirrored in JavaIdioms as of April 29, 2006