Higher-order function

In mathematics and computer science, a higher-order function (also functional, functional form or functor) is a function that does at least one of the following:

All other functions are first-order functions. In mathematics higher-order functions are also termed operators or functionals. The differential operator in calculus is a common example, since it maps a function to its derivative, also a function.

In the untyped lambda calculus, all functions are higher-order; in a typed lambda calculus, from which most functional programming languages are derived, higher-order functions that take one function as argument are values with types of the form .

General examples

Support in programming languages

Direct support

The examples are not intended to compare and contrast programming languages, but to serve as examples of higher-order function syntax

In the following examples, the higher-order function twice takes a function, and applies the function to some value twice. If twice has to be applied several times for the same f it preferably should return a function rather than a value. This is in line with the "don't repeat yourself" principle.

Python 2

>>> def twice(f):
...     return lambda x: f(f(x))

>>> def f(x):
...     return x + 3

>>> g = twice(f)
    
>>> print g(7)
13

Pascal

{$mode objfpc}
type fun = function(x:integer):integer;

function f(x:integer):integer;
begin
	f:= x+3;
end;

function g( func:fun; x:integer):integer;
begin
        g:= func(x)*func(x);
end;

begin
     write(g(@f, 7));
end.

F#

let twice f = f >> f

let f = (+) 3

twice f 7 |> printf "%A" // 13

C#

Func<Func<int, int>, int, int> twice = (func, i) => func(func(i));
Func<int, int> f = x => x + 3;

Console.WriteLine(twice(f, 7));

Haskell

twice :: (a -> a) -> (a -> a)
twice f = f . f

f :: Num a => a -> a
f = subtract 3

main :: IO ()
main = print (twice f 7) -- 1

Clojure

(defn twice [function x]
  (function (function x)))

(twice #(+ % 3) 7) ;13

In Clojure, "#" starts a lambda expression, and "%" refers to the next function argument.

Scheme

(define (add x y) (+ x y))
(define (f x)
  (lambda (y) (+ x y)))
(display ((f 3) 7))
(display (add 3 7))

In this Scheme example, the higher-order function (f x) is used to implement currying. It takes a single argument and returns a function. The evaluation of the expression ((f 3) 7) first returns a function after evaluating (f 3). The returned function is (lambda (y) (+ 3 y)). Then, it evaluates the returned function with 7 as the argument, returning 10. This is equivalent to the expression (add 3 7), since (f x) is equivalent to the curried form of (add x y).

Erlang

or_else([], _) -> false;
or_else([F | Fs], X) -> or_else(Fs, X, F(X)).

or_else(Fs, X, false) -> or_else(Fs, X);
or_else(Fs, _, {false, Y}) -> or_else(Fs, Y);
or_else(_, _, R) -> R.

or_else([fun erlang:is_integer/1, fun erlang:is_atom/1, fun erlang:is_list/1],3.23).

In this Erlang example, the higher-order function or_else/2 takes a list of functions (Fs) and argument (X). It evaluates the function F with the argument X as argument. If the function F returns false then the next function in Fs will be evaluated. If the function F returns {false,Y} then the next function in Fs with argument Y will be evaluated. If the function F returns R the higher-order function or_else/2 will return R. Note that X, Y, and R can be functions. The example returns false.


Elixir

In Elixir, you can mix module definitions and anonymous functions

defmodule Hop do
    def twice(f, v) do
        f.(f.(v))
    end
end

add3 = fn(v) -> 3 + v end

IO.puts Hop.twice(add3, 7) #13

Alternatively, we can also compose using pure anonymous functions.

twice = fn(f, v) -> f.(f.(v)) end
add3 = fn(v) -> 3 + v end

IO.puts twice.(add3, 7) #13


JavaScript

function twice(f, v) {
  return f(f(v));
}

function add3(v) {
  return v + 3;
}

console.log(twice(add3, 7)); // 13

Go

func twice(f func(int) int, v int) int {
	return f(f(v))
}

func main() {
	f := func(v int) int {
		return v + 3
	}
	twice(f, 7) // returns 13
}

Notice a function literal can be defined either with an identifier (twice) or anonymously (assigned to variable f). Run full program on Go Playground!

Scala

def twice(f:Int=>Int) = f compose f

twice(_+3)(7) // 13

Java (1.8+)

Function<Function<Integer, Integer>, Function<Integer, Integer>> twice = f -> f.andThen(f);
twice.apply(x -> x + 3).apply(7); // 13

Kotlin

fun <T> twice(f: (T)->T): (T)->T = {f(f(it))}
fun f(x:Int) = x + 3
println(twice(::f)(7)) // 13

Lua 

local twice = function(f,v)
    return f(f(v))
end

local f = function(v)
    return v + 3
end

print(twice(f,7)) -- 13

Swift

func twice(_ f: @escaping (Int) -> Int) -> (Int) -> Int { return { f(f($0)) } }

func f(_ arg: Int) -> Int { return arg + 3 }

let g = twice(f)
print(g(7)) // 13

Rust

// Take function f(x), return function f(f(x))
fn twice<A, F>(function: F) -> Box<Fn(A) -> A> 
    where F: 'static + Fn(A) -> A
{
    Box::new(move |a| function(function(a)))
}

// Return x + 3
fn f(x: i32) -> i32 {
    x + 3
}

fn main() {
    let g = twice(f);
    println!("{}", g(7));
}

C++

// Generic lambdas provided by C++14.
#include <iostream>

auto twice = [](auto f, int v)
{
    return f(f(v));
};
    
auto f = [](int i)
{
    return i + 3;
};
 
int main()
{   
    std::cout << twice(f, 7) << std::endl;
}

// Or, use std::function in C++11
#include <iostream>
#include <functional>

auto twice = [](const std::function<int(int)>& f, int v)
{
    return f(f(v));
};
    
auto f = [](int i)
{
    return i + 3;
};
    
int main()
{
    std::cout << twice(f, 7) << std::endl;
}

D

import std.stdio : writeln;

alias twice = (f, i) => f(f(i));
alias f = (int i) => i + 3;

void main()
{
    writeln(twice(f, 7));
}

ColdFusion Markup Language (CFML)

twice = function(f, v) {
    return f(f(v));
};

f = function(v) {
    return v + 3;
};

writeOutput(twice(f, 7)); // 13

PHP

$twice = function($f, $v) {
    return $f($f($v));
};

$f = function($v) {
    return $v + 3;
};

echo($twice($f, 7)); // 13

R

twice <- function(func) {
  return(function(x) {
    func(func(x))
  })
}

f <- function(x) {
  return(x + 3)
}

g <- twice(f)

> print(g(7))
[1] 13

Perl 6

sub twice(Callable:D $c) {
    return sub { $c($c($^x)) };
}

sub f(Int:D $x) {
    return $x + 3;
}

my $g = twice(&f);

say $g(7); #OUTPUT: 13

In Perl 6, all code objects are closures and therefore can reference inner "lexical" variables from an outer scope because the lexical variable is "closed" inside of the function. Perl 6 also supports "pointy block" syntax for lambda expressions which can be assigned to a variable or invoked anonymously.

Tcl

set twice {{f v} {apply $f [apply $f $v]}}
set f {{v} {return [expr $v + 3]}}

# result: 13
puts [apply $twice $f 7]

Tcl uses apply command to apply an anonymous function (since 8.6).

XACML

The XACML standard defines higher-order functions in the standard to apply a function to multiple values of attribute bags.

rule allowEntry{
    permit
    condition anyOfAny(function[stringEqual], citizenships, allowedCitizenships)
}

The list of higher-order functions is can be found here.

Alternatives

Function pointers

Function pointers in languages such as C and C++ allow programmers to pass around references to functions. The following C code computes an approximation of the integral of an arbitrary function:

#include <stdio.h>

double square(double x)
{
    return x * x;
}

double cube(double x)
{
    return x * x * x;
}

/* Compute the integral of f() within the interval [a,b] */
double integral(double f(double x), double a, double b, int n)
{
    int i;
    double sum = 0;
    double dt = (b - a) / n;
    for (i = 0;  i < n;  ++i) {
        sum += f(a + (i + 0.5) * dt);
    }
    return sum * dt;
}

int main()
{
    printf("%g\n", integral(square, 0, 1, 100));
    printf("%g\n", integral(cube, 0, 1, 100));
    return 0;
}

The qsort function from the C standard library uses a function pointer to emulate the behavior of a higher-order function.

Macros

Macros can also be used to achieve some of the effects of higher order functions. However, macros cannot easily avoid the problem of variable capture; they may also result in large amounts of duplicated code, which can be more difficult for a compiler to optimize. Macros are generally not strongly typed, although they may produce strongly typed code.

Dynamic code evaluation

In other imperative programming languages, it is possible to achieve some of the same algorithmic results as are obtained via higher-order functions by dynamically executing code (sometimes called Eval or Execute operations) in the scope of evaluation. There can be significant drawbacks to this approach:

Objects

In object-oriented programming languages that do not support higher-order functions, objects can be an effective substitute. An object's methods act in essence like functions, and a method may accept objects as parameters and produce objects as return values. Objects often carry added run-time overhead compared to pure functions, however, and added boilerplate code for defining and instantiating an object and its method(s). Languages that permit stack-based (versus heap-based) objects or structs can provide more flexibility with this method.

An example of using a simple stack based record in Free Pascal with a function that returns a function:

program example;

type 
  int = integer;
  Txy = record x, y: int; end;
  Tf = function (xy: Txy): int;
     
function f(xy: Txy): int; 
begin 
  Result := xy.y + xy.x; 
end;

function g(func: Tf): Tf; 
begin 
  result := func; 
end;

var 
  a: Tf;
  xy: Txy = (x: 3; y: 7);

begin  
  a := g(@f);     // return a function to "a"
  writeln(a(xy)); // prints 10
end.

The function a() takes a Txy record as input and returns the integer value of the sum of the record's x and y fields (3 + 7).

Defunctionalization

Defunctionalization can be used to implement higher-order functions in languages that lack first-class functions:

// Defunctionalized function data structures
template<typename T> struct Add { T value; };
template<typename T> struct DivBy { T value; };
template<typename F, typename G> struct Composition { F f; G g; };

// Defunctionalized function application implementations
template<typename F, typename G, typename X>
auto apply(Composition<F, G> f, X arg) {
    return apply(f.f, apply(f.g, arg));
}

template<typename T, typename X>
auto apply(Add<T> f, X arg) {
    return arg  + f.value;
}

template<typename T, typename X>
auto apply(DivBy<T> f, X arg) {
    return arg / f.value;
}

// Higher-order compose function
template<typename F, typename G>
Composition<F, G> compose(F f, G g) {
    return Composition<F, G> {f, g};
}

int main(int argc, const char* argv[]) {
    auto f = compose(DivBy<float>{ 2.0f }, Add<int>{ 5 });
    apply(f, 3); // 4.0f
    apply(f, 9); // 7.0f
    return 0;
}

In this case, different types are used to trigger different functions via function overloading. The overloaded function in this example has the signature auto apply.

See also

References

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.