I also received it all. Linda
-----Original Message----- From: programming-boun...@jsoftware.com [mailto:programming-boun...@jsoftware.com] On Behalf Of R.E. Boss 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
