Incomputer science,function composition is an act or mechanism to combine simplefunctions to build more complex ones. Like the usualcomposition of functions inmathematics, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole.
Programmers frequently apply functions to results of other functions, and almost all programming languages allow it. In some cases, the composition of functions is interesting as a function in its own right, to be used later. Such a function can always be defined but languages withfirst-class functions make it easier.
The ability to easily compose functions encouragesfactoring (breaking apart)functions for maintainability andcode reuse. More generally, big systems might be built by composing whole programs.
Narrowly speaking, function composition applies to functions that operate on a finite amount of data, each step sequentially processing it before handing it to the next. Functions that operate on potentially infinite data (astream or othercodata) are known asfilters, and are instead connected in apipeline, which is analogous to function composition and can executeconcurrently.
For example, suppose we have twofunctionsf andg, as inz =f(y) andy =g(x). Composing them means we first computey =g(x), and then usey to computez =f(y). Here is the example in theC language:
floatx,y,z;// ...y=g(x);z=f(y);
The steps can be combined if we don't give a name to the intermediate result:
z=f(g(x));
Despite differences in length, these two implementations compute the same result. The second implementation requires only one line of code and is colloquially referred to as a "highly composed" form. Readability and hence maintainability is one advantage of highly composed forms, since they require fewer lines of code, minimizing a program's "surface area".[1] DeMarco and Lister empirically verify an inverse relationship between surface area and maintainability.[2] On the other hand, it may be possible to overuse highly composed forms. A nesting of too many functions may have the opposite effect, making the code less maintainable.
In astack-based language, functional composition is even more natural: it is performed byconcatenation, and is usually the primary method of program design. The above example inForth:
g f
Which will take whatever was on the stack before, apply g, then f, and leave the result on the stack. Seepostfix composition notation for the corresponding mathematical notation.
Now suppose that the combination of callingf() on the result ofg() is frequently useful, and which we want to namefoo() to be used as a function in its own right.
In most languages, we can define a new function implemented by composition. Example inC:
floatfoo(floatx){returnf(g(x));}
(the long form with intermediates would work as well.) Example inForth:
: foo g f ;
In languages such asC, the only way to create a new function is to define it in the program source, which means that functions can't be composed atrun time. An evaluation of an arbitrary composition ofpredefined functions, however, is possible:
#include<stdio.h>typedefintFXN(int);intf(intx){returnx+1;}intg(intx){returnx*2;}inth(intx){returnx-3;}inteval(FXN*fs[],intsize,intx){for(inti=0;i<size;i++)x=(*fs[i])(x);returnx;}intmain(){// ((6 + 1) * 2) - 3 = 11FXN*arr[]={f,g,h};printf("%d\n",eval(arr,3,6));// ((6 - 3) * 2) + 1 = 7arr[2]=f;arr[0]=h;printf("%d\n",eval(arr,3,6));}
Infunctional programming languages, function composition can be naturally expressed as ahigher-order function or operator. In other programming languages you can write your own mechanisms to perform function composition.
InHaskell, the examplefoo =f ∘ g given above becomes:
foo = f . g
using the built-in composition operator (.) which can be read asf after g org composed with f.
The composition operator ∘ itself can be defined in Haskell using alambda expression:
(.)::(b->c)->(a->b)->a->cf.g=\x->f(gx)
The first line describes the type of (.) - it takes a pair of functions,f, g and returns a function (the lambda expression on the second line).Note that Haskell doesn't require specification of the exact input and output types of f and g; the a, b, c, and x are placeholders;only the relation betweenf, g matters (f must accept what g returns). This makes (.) apolymorphic operator.
A polymorphic operator with multiple arguments, in Haskell'spoint-free notation
fgxy
is[3]
(.).(.)
where the parameter names are immaterial,[3] as stated above. Michal Ševčík credits CScalfani with a systematic exposition forfunction composition using additional parameters.[4]
Variants ofLisp, especiallyScheme, theinterchangeability of code and data together with the treatment of functions lend themselves extremely well for a recursive definition of avariadic compositional operator.
(define(compose.fs)(if(null?fs)(lambda(x)x); if no argument is given, evaluates to the identity function(lambda(x)((carfs)((applycompose(cdrfs))x))))); examples(define(add-a-bangstr)(string-appendstr"!"))(definegivebang(composestring->symboladd-a-bangsymbol->string))(givebang'set); ===> set!; anonymous composition((composesqrt-sqr)5); ===> 0+5i
Many dialects ofAPL feature built in function composition using the symbol∘. This higher-order function extends function composition todyadic application of the left side function such thatA f∘g B isA f g B.
foo←f∘g
Additionally, you can define function composition:
o←{⍺⍺⍵⍵⍵}
In dialect that does not support inline definition using braces, the traditional definition is available:
∇r←(fog)xr←fgx∇
Raku likeHaskell has a built in function composition operator, the main difference is it is spelled as∘ oro.
my&foo=&f∘&g;
Also likeHaskell you could define the operator yourself. In fact the following is the Raku code used to define it in theRakudo implementation.
# the implementation has a slightly different line here because it cheatsprotosubinfix:<∘> (&?, &?) is equiv(&[~]) is assoc<left> {*}multisubinfix:<∘> () {*.self}# allows `[∘] @array` to work when `@array` is emptymultisubinfix:<∘> (&f) {&f}# allows `[∘] @array` to work when `@array` has one elementmultisubinfix:<∘> (&f, &g --> Block) {(&f).count>1??->|args{f|g|args}!!->|args{fg|args}}# alias it to the "Texas" spelling ( everything is bigger, and ASCII in Texas )my&infix:<o>:=&infix:<∘>;
Nim supportsuniform function call syntax, which allows for arbitrary function composition through the method syntax. operator.[5]
funcfoo(a:int):string=$afuncbar(a:string,count:int):seq[string]=foriin0..<count:result.add(a)funcbaz(a:seq[string])=foriina:echoi# equivalent!echofoo(5).bar(6).baz()echobaz(bar(6,foo(5)))
InPython, a way to define the composition for any group of functions, is usingfunctools.reduce function:
fromfunctoolsimportreducefromtypingimportCallabledefcompose(*funcs)->Callable[[int],int]:"""Compose a group of functions (f(g(h(...)))) into a single composite func."""returnreduce(lambdaf,g:lambdax:f(g(x)),funcs)# Examplef=lambdax:x+1g=lambdax:x*2h=lambdax:x-3# Call the function x=10 : ((x - 3) * 2) + 1 = 15print(compose(f,g,h)(10))
InJavaScript we can define it as a function which takes two functionsf andg, and produces a function:
functiono(f,g){returnfunction(x){returnf(g(x));}}// Alternatively, using the rest operator and lambda expressions in ES2015constcompose=(...fs)=>(x)=>fs.reduceRight((acc,f)=>f(acc),x)
InC# we can define it as an Extension method which takes Funcsf andg, and produces a newFunc:
// Call example:// var c = f.ComposeWith(g);//// Func<int, bool> g = _ => ...// Func<bool, string> f = _ => ...publicstaticFunc<T1,T3>ComposeWith<T1,T2,T3>(thisFunc<T2,T3>f,Func<T1,T2>g)=>x=>f(g(x));
Languages likeRuby let you construct a binary operator yourself:
classProcdefcompose(other_fn)->(*as){other_fn.call(call(*as))}endalias_method:+,:composeendf=->(x){x*2}g=->(x){x**3}(f+g).call(12)# => 13824
However, a native function composition operator was introduced in Ruby 2.6:[6]
f=proc{|x|x+2}g=proc{|x|x*3}(f<<g).call(3)# -> 11; identical to f(g(3))(f>>g).call(3)# -> 15; identical to g(f(3))
Notions of composition, including theprinciple of compositionality andcomposability, are so ubiquitous that numerous strands of research have separately evolved. The following is a sampling of the kind of research in which the notion of composition is central.
Whole programs or systems can be treated as functions, which can be readily composed if their inputs and outputs are well-defined.[7]Pipelines allowing easy composition offilters were so successful that they became adesign pattern of operating systems.
Imperative procedures with side effects violatereferential transparency and therefore are not cleanly composable. However if one considers the "state of the world" before and after running the code as its input and output, one gets a clean function. Composition of such functions corresponds to running the procedures one after the other. Themonad formalism uses this idea to incorporate side effects and input/output (I/O) into functional languages.