Boss' reply in the archives also includes the complete original post text, confirming Tracy's conjecture. ________________________________________ From: programming-boun...@jsoftware.com [programming-boun...@jsoftware.com] on behalf of R.E. Boss [r.e.b...@planet.nl] Sent: Monday, April 02, 2012 3:02 AM To: 'Programming forum' Subject: Re: [Jprogramming] Functors in mathematics, Haskell and an example in J
I received what appears to be all of your text, more than is in the archives. See below your original first post . R.E. Boss > -----Oorspronkelijk bericht----- > Van: programming-boun...@jsoftware.com > [mailto:programming-boun...@jsoftware.com] Namens Boyko Bantchev > Verzonden: zondag 1 april 2012 23:42 > Aan: Programming forum > Onderwerp: Re: [Jprogramming] Functors in mathematics, Haskell and an example > in J > > Reading Viktor's post, I found myself provoked by some – in my > opinion – omissions and inaccuracies in his definitions. > He also has a different perspective on how categories apply to > programming and to Haskell in particular, to which I tend to > partially disagree. > > Instead of, as I originally intended, just commenting on specific > topics, I set about describing what functors and related concepts are > in category theory, how they map to Haskell, and how they are being > used in that language. The resulting text is longer than I would > like it, but, hopefully, it clarifies the topic with sufficient > detail and so can be useful in some ways to J-ers. > > Categories and functors > *********************** > > A category consists of two kinds of entities: objects and morphisms, > a.k.a. arrows. Each arrow maps one single object to another (in the > same category), and is what we call a function in other contexts. > Arrows can be composed one after another, thus producing new arrows. > > The arrows of a category furnish it with structure by relating > its objects to each other. Arrows, in turn, are related through > composition, so the latter plays an important role in respect of > the category's structure. > > It is often the case that the objects and arrows of a category come > from some other domain of consideration. However, from the perspective > of the category, neither of them has an internal structure or whatever > properties of their own. Being the domain or codomain of arrows is > the only thing at all that an object can be in its category, and an > arrow is nothing more than a link from one object to another. > > A functor is a mapping from one category, A, to another (or sometimes > the same), B. It consists of two maps – one from the objects of A to > those of B, and another from the arrows of A to those of B. Now, we > expect a functor to not just be an arbitrary mapping, but also to > correlate the structure of its domain category (A) to that of the > codomain (B). To this end, the arrow part of the functor, let's call > it Fa, has to obey, for each pair of arrows f and g in A, the identity > > Fa (f∘g) ≡ (Fa f) ∘ (Fa g) > > which means that the image in B of the composition f∘g in A is > precisely the composition of the images of f and g (the latter > composition taking place in B). Or, shortly put: the image of a > composition is the composition of images. We could also say that > 'Fa distributes over ∘', in the same sense that multiplication > distributes over addition in arithmetic. > > There is one more property for Fa to obey – it is so simple and > obviously necessary that it is easy to remain unnoticed, but it > has to be stated explicitly: Fa has to also 'distribute' over the > identity arrows: if i(x) is the arrow from x to itself in A, then > > Fa i(x) ≡ i(Fa x) , > > where i(Fa x) is the arrow from Fa x to itself. > > In the sense of the above two axioms, a functor is a structure- > preserving operation on categories. > > Categories and functors in Haskell > ********************************** > > In Haskell, the concept of a functor is very close to the one in the > category theory. Of course, this is an empty statement unless we know > what in Haskell corresponds to categories, objects, and arrows. So, > first things first. > > Think of datatypes as objects of which categories are constructed. > We can imagine one universal category whose objects are all the > datatypes of a programming language (here, Haskell). Correspondingly, > each function is an arrow in this category. > > Data structures, such as lists, trees etc., are usually represented > as datatypes. But, in a typed language, one cannot have a data object > that is simply 'a list', there must be specified 'a list of integers' > or similar. So, from each data structure emerges a family of concrete > types with the same organization but different types of elements. It > makes sense to think of such a family as parameterized by its element > type. It is therefore useful to associate with the type family a > function which, given a datatype, produces another type – a member of > the family. In Haskell, this concept is embodied in the so called > 'type constructors', or 'tycons' for short. > > From a categorial point of view, to each family of types as described > above, there corresponds a category (whose objects are the members of > the family). Thus there are categories of lists, of trees, etc. > The objects of the category of lists are the types of integer-valued, > real-valued, string-valued, etc. lists. > > Note that there is a one-to-one correspondence between tyconses and > categories (except the universal category), naturally established > through both being associated with the same family of types. > > As any other value, functions are typed, and their types are written > f :: a -> b, meaning that the function f has a domain a and a codomain > b. Because there can be many functions of the same signature a -> b, > there are many arrows between any two objects in any of the categories, > the universal one or the specific. > > After all this, what is a functor in Haskell? It is a mapping, in > the above described categorial sense of the word 'functor', from the > universal category of types to any one of the specific categories. > The definition of functor is embodied in the following type class > interface: > > class Functor t where > fmap :: (a -> b) -> (t a -> t b) > > together with the axioms > > fmap id ≡ id > fmap (f . g) ≡ fmap f . fmap g > > In the above interface, t represents a dummy tycon for which a > function fmap is defined that has the given signature and satisfies > the axioms. fmap transforms any function into a function whose domain > and codomain are types produced by that constructor. (Given that the > original function's domain and codomain are a and b, fmap produces a > function whose domain and codomain are the types (t a) and (t b).) > In this way, fmap 'adapts' general functions for use within the data > structure represented by the tycon. > > E.g., the t can be the tycon of lists which, given a type x, produces > a list with element type x. That t is made an instance of Functor by > trivially defining fmap to be the library function 'map' which, given > a function f, creates a function that transforms a list by applying f > to each of its elements. > > A tycon for which fmap exists is often, informally, called a functor. > Strictly speaking, it implements a functor with codomain the tycon's > respective category. > > Note that fmap only represents the arrow part of the functor. The > object part is implicit. It must also be stressed that satisfying > the axioms is not (and could not be) automatic – ensuring that they > are valid for a specific implementation of fmap is a programmer's > obligation! > > Functors in J? > ************** > > The observed correspondence between category theory and Haskell can > be summarized in the following table. > > category theory Haskell > --------------------------------------------------------------------- > category the universal category of types; > specific categories (families of datatypes) > > category constructor type constructor > > object type > > arrow function > > composition of arrows composition of functions > > definition of functor Functor interface and axioms > as concept > > functor axioms-complying implementation of Functor > (associated with a specific tycon) > > If we can build a similar table with J in the right column, we can > say that we have an idea what might be a J's version of functors in > general. > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm [BEST LLC] Bayesian Efficient Strategic Trading LLC The information in this communication and any attachment is confidential and intended solely for the attention and use of the named addressee(s). Any views or opinions presented are solely those of the author and do not necessarily represent those of BEAM Bayesian Efficient Asset Management, LLC (BEAM), Bayesian Efficient Strategic Trading, LLC (BEST) and/or their affiliates unless otherwise specifically stated. All information and opinions expressed herein are subject to change without notice. This communication is not to be construed as an offer to sell or the solicitation of an offer to buy any security. Any reliance one may place on the accuracy or validity of this information is at their own risk. Past performance is not necessarily indicative of the future results of an investment. If you are not the intended recipient, or a person responsible for delivering this to the intended recipient, you are not authorized to and must not disclose, copy, distribute, or retain this message or any part of it. If you are not the intended recipient, please permanently delete all copies of this communication and any attachments from your computer system, destroy any hard copies, and immediately notify the sender or BEAM/BEST at either i...@2bestsystems.com, i...@beamstrategy.com or (201) 792-1002. No waiver of confidentiality or privilege is made by mistransmission. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
