Editing Function type

In [[computer science]] and [[mathematical logic]], a '''function type''' (or '''arrow type''' or '''exponential''') is the type of a [[variable (computer science)|variable]] or [[parameter (computer science)|parameter]] to which a [[function (computer science)|function]] has or can be assigned, or an argument or result type of a [[higher-order function]] taking or returning a function.

A function type depends on the type of the parameters and the result type of the function (it, or more accurately the unapplied [[type constructor]] <code>{{nowrap|· → ·}}</code>, is a [[higher-kinded type]]). In theoretical settings and [[programming language]]s where functions are defined in [[curried form]], such as the [[simply typed lambda calculus]], a function type depends on exactly two types, the [[domain of a function|domain]] ''A'' and the [[range of a function|range]] ''B''. Here a function type is often denoted {{math|''A'' → ''B''}}, following mathematical convention, or {{math|''B''<sup>''A''</sup>}}, based on there existing exactly {{math|''B''<sup>''A''</sup>}} (exponentially many) [[function space|set-theoretic functions]] mappings ''A'' to ''B'' in the [[category of sets]]. The class of such maps or functions is called the [[exponential object]]. The act of [[currying]] makes the function type [[adjoint functor|adjoint]] to the [[product type]]; this is explored in detail in the article on currying.

The function type can be considered to be a special case of the [[Dependent type#Formal definition|dependent product type]], which among other properties, encompasses the idea of a [[polymorphism (computer science)|polymorphic function]].

== Programming languages ==
The syntax used for function types in several programming languages can be summarized, including an example type signature for the higher-order [[function composition (computer science)|function composition]] function:
{| class=wikitable
|-
! colspan=2 | Language !! Notation !! Example [[type signature]]
|-
| rowspan=7 | With [[first-class function]]s,<br> [[parametric polymorphism]]
| [[C Sharp (programming language)|C#]]
| <code>Func<''α''<sub>1</sub>,''α''<sub>2</sub>,...,''α''<sub>''n''</sub>,''ρ''></code>
| {{code|2=csharp|Func<A,C> compose(Func<B,C> f, Func<A,B> g);}}
|-
| [[Haskell (programming language)|Haskell]]
| <code>''α'' -> ''ρ''</code>
| {{code|2=haskell|compose :: (b -> c) -> (a -> b) -> a -> c}}
|-
| [[OCaml]]
| <code>''α'' -> ''ρ''</code>
| {{code|2=ocaml|compose : ('b -> 'c) -> ('a -> 'b) -> 'a -> 'c}}
|-
| [[Scala (programming language)|Scala]]
| <code>(''α''<sub>1</sub>,''α''<sub>2</sub>,...,''α''<sub>''n''</sub>) => ''ρ''</code>
| {{code|2=scala|1=def compose[A, B, C](f: B => C, g: A => B): A => C }}
|-
| [[Standard ML]]
| <code>''α'' -> ''ρ''</code>
| {{code|2=sml|compose : ('b -> 'c) -> ('a -> 'b) -> 'a -> 'c}}
|-
| [[Swift (programming language)|Swift]]
| <code>''α'' -> ''ρ''</code>
| {{code|2=swift|func compose<A,B,C>(f: (B) -> C, g: (A) -> B) -> (A) -> C}}
|-
| [[Rust (programming language)|Rust]]
| <code>fn(''α''<sub>1</sub>,''α''<sub>2</sub>,...,''α''<sub>''n''</sub>) -> ''ρ''</code>
| {{code|2=rust|fn compose<A, B, C>(f: fn(A) -> B, g: fn(B) -> C) -> fn(A) -> C}}
|-
| rowspan=2 |  With [[first-class function]]s,<br> without [[parametric polymorphism]]
| [[Go (programming language)|Go]]
| <code>func(''α''<sub>1</sub>,''α''<sub>2</sub>,...,''α''<sub>''n''</sub>) ''ρ''</code>
| {{code|2=go|var compose func(func(int)int, func(int)int) func(int)int}}
|-
| [[C++]], [[Objective-C]], with [[Blocks (C language extension)|blocks]]
| <code>''ρ'' (^)(''α''<sub>1</sub>,''α''<sub>2</sub>,...,''α''<sub>''n''</sub>)</code>
| {{code|2=objc|int (^compose(int (^f)(int), int (^g)(int)))(int);}}
|-
| rowspan=2 | Without [[first-class function]]s,<br> [[parametric polymorphism]]
| [[C (programming language)|C]]
| <code>''ρ'' (*)(''α''<sub>1</sub>,''α''<sub>2</sub>,...,''α''<sub>''n''</sub>)</code>
| {{code|2=c|int (*compose(int (*f)(int), int (*g)(int)))(int);}}
|-
| [[C++11]]
| Not unique.
<code>std::function<''ρ'' (''α''<sub>1</sub>,''α''<sub>2</sub>,...,''α''<sub>''n''</sub>)></code> is the more general type (see below).
| {{code|2=cpp|function<function<int(int)>(function<int(int)>, function<int(int)>)> compose;}}

|}

When looking at the example type signature of, for example C#, the type of the function {{code|compose}} is actually <code>Func<Func<A,B>,Func&lt;B,C>,Func<A,C>></code>.

Due to [[type erasure]] in C++11's <code>std::function</code>, it is more common to use [[Template (C++)|templates]] for [[higher order function]] parameters and [[type inference]] (<code>auto</code>) for [[Closure (computer programming)|closures]].

== Denotational semantics ==
The function type in programming languages does not correspond to the space of all set-theoretic functions. Given the [[countably infinite]] type of [[natural number]]s as the domain and the booleans as range, then there are an [[uncountably infinite]] number (2<sup>ℵ<sub>0</sub></sup> = [[Cardinality of the continuum|c]]) of set-theoretic functions between them. Clearly this space of functions is larger than the number of functions that can be defined in any programming language, as there exist only countably many programs (a program being a finite sequence of a finite number of symbols) and one of the set-theoretic functions effectively solves the [[halting problem]].

[[Denotational semantics]] concerns itself with finding more appropriate models (called [[domain theory|domains]]) to model programming language concepts such as function types. It turns out that restricting expression to the set of [[computable function]]s is not sufficient either if the programming language allows writing [[non-terminating computation]]s (which is the case if the programming language is [[Turing complete]]). Expression must be restricted to the so-called ''[[Continuous functions#Continuous functions between partially ordered sets|continuous functions]]'' (corresponding to continuity in the [[Scott topology]], not continuity in the real analytical sense). Even then, the set of continuous function contains the ''parallel-or'' function, which cannot be correctly defined in all programming languages.

== See also ==
* [[Cartesian closed category]]
* [[Currying]]
* [[Exponential object]], category-theoretic equivalent
* [[First-class function]]
* [[Function space]], set-theoretic equivalent

== References ==
* {{cite book|first=Benjamin C.|last=Pierce|authorlink=Benjamin C. Pierce|title=Types and Programming Languages|year=2002|url=https://archive.org/details/typesprogramming00pier_207|url-access=limited|publisher=The MIT Press|pages=[https://archive.org/details/typesprogramming00pier_207/page/n122 99]–100|isbn=9780262162098 }}
* {{cite book|first=John C.|last=Mitchell|authorlink=John C. Mitchell|title=Foundations for Programming Languages|publisher=The MIT Press}}
* {{nlab|id=function+type|title=function type}}
* [http://homotopytypetheory.org/2013/06/20/the-hott-book/ ''Homotopy Type Theory: Univalent Foundations of Mathematics'', The Univalent Foundations Program, Institute for Advanced Study]. ''See section 1.2''.

{{Data types}}

[[Category:Data types]]
[[Category:Subroutines]]
[[Category:Type theory]]