In a programming language, a function which accepts a function as an argument, or returns a function, or both. Most languages which let you do one let you do the other. Being able to return functions is much more useful if you can dynamically generate them. HOFs are a prerequisite for currying. You can't really call a language functional if it doesn't allow for HOFs.
Languages which have HOFs of some variety or another include C, Haskell, LISP, Perl, Ruby, and Scheme.
Examples
In each example, a function foo is defined which accepts as its argument a function f (which takes two arguments), and returns a new function which is identical to f except that it takes its arguments the other way around. We then use foo to subtract one number from another, the backwards way.
Scheme:
(define (foo f)
(lambda (a b) (f b a)))
((foo -) 3 8)
; the idea can be generalised further:
(define (bar f)
(lambda list (apply f (reverse list))))
((bar -) 3 6 11)
; yields 2 (i.e. (- 11 6 3))
Haskell:
foo :: (a -> b -> c) -> (b -> a -> c)
foo f = \x y -> f y x
foo (-) 3 8
Perl:
Since Perl's "-" is an operator, not a function, we define our own subtraction function, called "minus".
sub foo
{
my $f = shift;
return sub { $f->($_[1], $_[0]) };
}
sub minus { $_[0] - $_[1] }
foo(\&minus)->(3, 8);
See also currying, anonymous functions, map, grep, qsort.
The above code has been tested and Works For Me™ - let me know if it doesn't for you.