Fano resonance: Difference between revisions
en>Nanite |
|||
Line 1: | Line 1: | ||
{{DISPLAYTITLE:''F''-algebra}} | |||
In [[mathematics]], specifically in [[category theory]], an '''''F''-algebra''' is a structure defined according to a (endo-)[[functor]] ''F''. ''F''-algebras can be used to represent [[data structures]] used in [[Mathematical programming|programming]], such as [[List (computing)|list]]s and trees. Initial ''F''-algebras encapsulate an induction principle. | |||
''F''-algebras are dual to [[F-coalgebra|''F''-coalgebra]]s. | |||
[[File:Commutative diagram defining F-algebra.png|thumb|The commutative diagram, which defines a property required by morphisms of the original category, so that they can be morphism of the newly defined category of ''F''-algebras.]] | |||
==Definition== | |||
If <math>\mathcal{C}</math> is a [[category (mathematics)|category]], and | |||
:<math>F : \mathcal{C}\longrightarrow \mathcal{C}</math> | |||
is an [[endofunctor]] of <math>\mathcal{C}</math>, then an '''''F''-algebra''' is an object <math>A</math> of <math>\mathcal{C}</math> together with a <math>\mathcal{C}</math>-[[morphism]] | |||
:<math>\alpha : F(A) \longrightarrow A</math>. | |||
In this sense ''F''-algebras are dual to ''F''-coalgebras. | |||
A [[homomorphism]] from an ''F''-algebra <math>(A, \alpha)</math> to an ''F''-algebra <math>(B, \beta)</math> is a <math>\mathcal{C}</math>-morphism | |||
:<math>f:A\longrightarrow B</math> | |||
such that | |||
:<math> f\circ \alpha = \beta \circ F(f)</math>, | |||
see picture. | |||
Thus the ''F''-algebras constitute a category. | |||
== Example == | |||
Consider the functor <math>F: \mathbf{Set} \to\mathbf{Set}</math> that sends a set <math>X</math> to <math>1+X</math>. Here, '''Set''' denotes the [[category of sets]], <math>+</math> denotes the usual [[coproduct]] given by [[disjoint union]], and 1 is a terminal object (i.e. any singleton set). Then the set '''N''' of [[natural number]]s together with the function <math>[\mathrm{zero},\mathrm{succ}] : 1+\mathbb{N} \to \mathbb{N}</math>, which is the coproduct of the functions <math>\mathrm{zero} : 1 \to \mathbb{N}</math> (whose image is ''0'') and <math> \mathrm{succ} : \mathbb{N} \to \mathbb{N}</math> (which sends an integer ''n'' to ''n+1''), is an ''F''-algebra. | |||
== Initial ''F''-algebra == | |||
{{main|Initial algebra}} | |||
If the category of ''F''-algebras for a given endofunctor ''F'' has an [[initial object]], it is called an '''initial algebra'''. The algebra <math>(\mathbb{N}, [\mathrm{zero},\mathrm{succ}])</math> in the above example is an initial algebra. Various [[finite set|finite]] [[data structures]] used in [[Mathematical programming|programming]], such as [[List (computing)|list]]s and trees, can be obtained as initial algebras of specific endofunctors. | |||
Types defined by using [[least fixed point]] construct with functor F can be regarded as an initial ''F''-algebra, provided that [[parametricity]] holds for the type.<ref name=free-rectypes>Philip Wadler: [http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt Recursive types for free!] University of Glasgow, June 1990. Draft. | |||
</ref> | |||
See also [[Universal algebra]]. | |||
== Terminal ''F''-coalgebra == | |||
In a [[Duality (mathematics)|dual]] way, similar relationship exists between notions of [[greatest fixed point]] and terminal ''F''-coalgebra, these can be used for allowing [[Actual infinity|potentially infinite]] objects while maintaining [[Normalization property (lambda-calculus)|strong normalization property]].<ref name=free-rectypes/> In the strongly normalizing [[Charity (programming language)|Charity]] programming language (i.e. each program terminates in it), [[Coinduction|coinductive]] data types can be used achieving surprising results, e.g. defining [[Lookup table|lookup]] constructs to implement such [[Computability theory (computer science)|“strong”]] functions like the [[Ackermann function]].<ref>Robin Cockett: Charitable Thoughts ([ftp://ftp.cpsc.ucalgary.ca/pub/projects/charity/literature/papers_and_reports/charitable.ps ps] and [ftp://ftp.cpsc.ucalgary.ca/pub/projects/charity/literature/papers_and_reports/charitable.ps.gz ps.gz])</ref> | |||
== See also == | |||
* [[Algebraic data type]] | |||
* [[Catamorphism]] | |||
== Notes == | |||
<references/> | |||
== Further reading == | |||
* {{cite book|first=Benjamin C.|last=Pierce|authorlink=Benjamin C. Pierce|title=Basic Category Theory for Computer Scientists|chapter=''F''-Algebras|isbn=0-262-66071-7}} | |||
== External links == | |||
* [http://www.cs.ut.ee/~varmo/papers/thesis.pdf Categorical programming with inductive and coinductive types] by Varmo Vene | |||
* Philip Wadler: [http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt Recursive types for free!] University of Glasgow, June 1990. Draft. | |||
* [http://tunes.org/wiki/algebra_20and_20coalgebra.html Algebra and coalgebra] from CLiki | |||
* B. Jacobs, J.Rutten: [http://www.cs.ru.nl/~bart/PAPERS/JR.pdf A Tutorial on (Co) Algebras and (Co) Induction. Bulletin of the European Association for Theoretical Computer Science], vol. 62, 1997 | |||
[[Category:Category theory]] | |||
[[Category:Functional programming]] |
Latest revision as of 11:04, 1 February 2014
In mathematics, specifically in category theory, an F-algebra is a structure defined according to a (endo-)functor F. F-algebras can be used to represent data structures used in programming, such as lists and trees. Initial F-algebras encapsulate an induction principle.
F-algebras are dual to F-coalgebras.
Definition
If is a category, and
is an endofunctor of , then an F-algebra is an object of together with a -morphism
In this sense F-algebras are dual to F-coalgebras.
A homomorphism from an F-algebra to an F-algebra is a -morphism
such that
see picture.
Thus the F-algebras constitute a category.
Example
Consider the functor that sends a set to . Here, Set denotes the category of sets, denotes the usual coproduct given by disjoint union, and 1 is a terminal object (i.e. any singleton set). Then the set N of natural numbers together with the function , which is the coproduct of the functions (whose image is 0) and (which sends an integer n to n+1), is an F-algebra.
Initial F-algebra
Mining Engineer (Excluding Oil ) Truman from Alma, loves to spend time knotting, largest property developers in singapore developers in singapore and stamp collecting. Recently had a family visit to Urnes Stave Church.
If the category of F-algebras for a given endofunctor F has an initial object, it is called an initial algebra. The algebra in the above example is an initial algebra. Various finite data structures used in programming, such as lists and trees, can be obtained as initial algebras of specific endofunctors.
Types defined by using least fixed point construct with functor F can be regarded as an initial F-algebra, provided that parametricity holds for the type.[1]
See also Universal algebra.
Terminal F-coalgebra
In a dual way, similar relationship exists between notions of greatest fixed point and terminal F-coalgebra, these can be used for allowing potentially infinite objects while maintaining strong normalization property.[1] In the strongly normalizing Charity programming language (i.e. each program terminates in it), coinductive data types can be used achieving surprising results, e.g. defining lookup constructs to implement such “strong” functions like the Ackermann function.[2]
See also
Notes
Further reading
- 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
External links
- Categorical programming with inductive and coinductive types by Varmo Vene
- Philip Wadler: Recursive types for free! University of Glasgow, June 1990. Draft.
- Algebra and coalgebra from CLiki
- B. Jacobs, J.Rutten: A Tutorial on (Co) Algebras and (Co) Induction. Bulletin of the European Association for Theoretical Computer Science, vol. 62, 1997