Content deleted Content added
Hairy Dude (talk | contribs) →Generalization: rewrite and expand category-theoretic comparison |
Hairy Dude (talk | contribs) m →Category-theoretic background: oops, fix type of fmap |
||
Line 78:
=== Category-theoretic background ===
In [[category theory]], a [[functor]] <math>F : C \rarr D</math> consists of two maps: one that sends each object <math>A</math> of the category to another object <math>F A</math>, and one that sends each morphism <math>f : A \rarr B</math> to another morphism <math>Ff : FA \rarr FB</math>, which acts as a [[homomorphism]] on categories (i.e. it respects the category axioms). Interpreting the universe of data types as a category <math>Type</math>, with morphisms being functions, then a type constructor <code>F</code> that is a member of the <code>Functor</code> type class is the object part of such a functor, and <code>fmap :: (a -> b) -> F a -> F b</code> is the morphism part. The functor laws described above are precisely the category-theoretic functor axioms for this functor.
Functors can also be objects in categories, with "morphisms" called [[natural transformation]]s. Given two functors <math>F, G : C \rarr D</math>, a natural transformation <math>\eta : F \rarr G</math> consists of a collection of morphisms <math>\eta_A : FA \rarr GA</math>, one for each object <math>A</math> of the category <math>D</math>, which are 'natural' in the sense that they act as a 'conversion' between the two functors, taking no account of the objects that the functors are applied to. Natural transformations correspond to functions of the form <code>eta :: F a -> G a</code>, where <code>a</code> is a universally quantified type variable – <code>eta</code> knows nothing about the type which inhabits <code>a</code>. The naturality axiom of such functions is automatically satisfied because it is a so-called free theorem, depending on the fact that it is [[parametric polymorphism|parametrically polymorphic]].<ref>In a [[non-strict language]] that permits general recursion, such as Haskell, this is only true if the first argument to <code>fmap</code> is strict. {{cite conference |title=Theorems for free! |first=Philip |last=Wadler |author-link=Philip Wadler |conference=4th International Symposium on Functional Programming Languages and Computer Architecture |___location=London |date=September 1989 |url=https://people.mpi-sws.org/~dreyer/tor/papers/wadler.pdf |publisher=[[Association for Computing Machinery]]}}</ref> For example, <code>reverse :: List a -> List a</code>, which reverses a list, is a natural transformation, as is <code>flattenInorder :: Tree a -> List a</code>, which flattens a tree from left to right, and even <code>sortBy :: (a -> a -> Bool) -> List a -> List a</code>, which sorts a list based on a provided comparison function.
| |||