First caution: the forum archived copy of this message
(http://jsoftware.com/pipermail/programming/2012-April/027795.html)
was arbitrarily truncated by some mail handling software. The first
complete instance of the text seems to be the response at
http://jsoftware.com/pipermail/programming/2012-April/027804.html
Second caution: I think that this is a very solid effort, for
explaining the issues relevant to understanding functors in the
context of J. I do not recall seeing better. However, I have some
difficulties with it, which may be difficulties with the underlying
concepts. No one should take my having these difficulties as a
personal affront.
I am going to annotate Boyko's original text with some questions, and
then I will come back to my understandings of the related issues after
his text.
On Sun, Apr 1, 2012 at 5:41 PM, Boyko Bantchev <boyk...@gmail.com> wrote:
> 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.
Q1: What is an object?
Q2: What does this "single object" constraint mean?
Q3: (only relevant in the context of the above two questions): What is
a function or arrow or morphism, here?
> 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)
Q4: is the above saying that a category can be an object? If so, what
does that tell us when combined with our answers to my previous
questions. (This question is not interesting to me without those
answers.)
> 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.
I note here that we are using the concept of "an image in a domain".
This tells us a part of the answer for Q1. It also raises some other
questions for me.
> 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) ,
Q5: In the opening paragraphs, arrows were defined between two
different objects. Do we have here a requirement for arrows that map
from an object to itself? Also, what does it mean if we have an arrow
from x to x and an arrow from Fa x to Fa x and they are "the same
arrow"? [This is probably just an english grammar issue.]
> 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.
Q6: A type family has an arbitrarily large number of members (and this
number can probably be infinite if we are talking about math instead
of Haskell). Does it matter which member of the family we produce in
a tycons?
> 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: partial answer to Q1 here.
> 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)
Note: this part of the definition of fmap looks very much like the J
concept of an adverb. (But it could also be a verb that accepts a
gerund argument and produces a gerund result, for the case where the
gerunds we are considering in both the verb's domain and codomain each
represent only one verb.)
> together with the axioms
>
> fmap id ≡ id
> fmap (f . g) ≡ fmap f . fmap g
And this part of the definition of fmap tells us that only some
adverbs (or verbs) can be valid fmaps.
> 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!
This stressed aspect fits J well enough: It's up to the programmer to
ensure that the adverb (or whatever) being defined is a valid fmap.
> 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.
So... back to my questions:
Q1: "what is an object"?
We know that an object is something that in some way corresponds to a
function's argument, or its domain. So, I might have a function which
maps from R3 to R3 (R3 being: three independent real numbers). Is R3
an object? I might instead have a function which maps from Z3 to Z3
(Z3 being: three independent complex numbers), or I3 to I3. Is this
the same function, or do we have to have a different function every
time we have a different domain?
Let's consider some example functions:
F1: result is always the single integer 0 regardless of its argument.
F2: 1 + its argument
F3: the largest integer N where N is strictly less than its argument
F1 can be made to work with any domain bit has a restricted codomain
F2 has a domain which can only be numeric and probably has no identity element
F3 has a restricted domain (I think it cannot include sequences of numbers)
In other words:
F1(1.5) would be 0
F1(1j1) would be 0
F1('this is a test') would be 0
F2(1.5) would be 2.5
F2(1j1) would be 2j1
F1('this is a test') would not be valid
F3(1.5) would be 1
F3(1j1) would not be valid
F3('this is a test') would not be valid
So what are the objects here?
If I say that the objects are the domains, then it's clear
that each of these functions have different domains. But
this creates a problem for me: F1 is valid for the domain
of F3. How am I to understand this in the context of "Each
arrow maps one single object to another (in the same category)"
Alternatively, I could say that each argument and each result is an
object. So, 1 is an object, 2 is an object, 1j1 is an object, 1 2 3
is an object, and so on. One variation of this approach is that I
have an infinity of arrows. The arrow from 1->2 is different from the
arrow from 2->3. But this means that F2 is not an arrow but a
potentially infinite collection of arrows.
Another approach to take is that arrows connect many objects and the
"single object" constraint means that each object in the domain
connects to only one object in the codomain. I think that this
variation best fits the description here.
Put differently: a domain is a set (as is a codomain), and an object
is a member of that set, and an arrow is a function on members of the
set. Domains can easily be infinitely large (in math) or can have
members which nearly fill a computer's memory (in programming). If we
are dealing with arbitrary functions, each function can have a domain
which does not match that of another function. And, distinct domains
can have non-empty intersections.
Q2 -- in the point of view I have expressed here, the answer to Q2 is
that arrows are functions and not more general relationships.
Q3 has no special answer here. A function is just a function -- all
the complexity has gone into the definition of the functions' domains
and the definitions of the individual functions. (This would have
been more complicated if we said that a function was the thing that
mapped a single object to a single object -- that each such mapping
was a different function.)
Q4 from my current viewpoint: a category need not be an object but
could be a (potentially infinite) collection of objects. But it could
be an object also. An infinite set can be an object, so it stands to
reason that size has nothing to do with "objectness". So this was not
an interesting question.
Q5: No: We do not have a requirement that a function have an identity
element. Thus, we can treat "not" operation on the smallest possible
logical domain as a function (true = not false, false = not true).
This constraint only applies when there is an identity.
As for the grammatical issue: if we have an identity operation i for
an arrow, this means that the fmap of that arrow has to have an
identity operation and it has to have an identity element which is the
mapped version of the original domain's identity element (for every
identity element in the original domain).
For example: a mapping from arbitrary function F4 to my previously
defined F1 would be a valid fmap.
Q6 seems like a slippery issue to me. On the one hand, I have not
seen anything explicitly stating that the member being constructed
matters (other than the identity element constraint, from Q5). On the
other hand, the use of fmap to represent a transformation on leaves of
a tree structure suggests that there must be very strong constraints
on the member being constructed. So obviously I am missing something
here.
But let's take a step back and consider some likely candidates for J functors.
First off "n is probably a functor for valid integer values of n.
Also &.> and L:n are probably functors. In fact &.g is probably a
functor, if g is limited sufficiently. :: g is probably also a
functor in the sense that f :: g an identity transform over the
original domain of f (f :: g derives a new function which is identical
to f over f's original domain and is identical to g over some other
domain).
I suppose the issue which concerns me is that &.g isn't a general
structure access mechanism in J. We could instead use 2 :'(u@)(@v)'
and we still don't have anything like a J structural definition or
structure access mechanism.
One issue here seems to me to be that while Haskell uses currying
routinely to express routine issues like argument passing and list
traversing, currying has a more limited role in J. In J, we derive
new verbs when we are using adjectives and conjunctions but unless we
are dealing with gerunds we probably do not derive new verbs when
evaluating verbs -- even [especially?] when we are dealing with lists
of data. (Then again, we can think of a lookup table as a function,
so perhaps I should state this differently.)
Another issue is that every J verb has a rank. So, in some sense you
can't have a J function without having a canned functor associated
with it.
Another issue is that in J we have nouns (and verbs, adverbs and
conjunctions) for our type system. Nouns are quite expressive but
ultimately they are a single data type. From a J point of view, when
we are reasoning about types, we are typically dealing with subsets of
the values which can be represented using nouns.
So, perhaps, for J users [like me] to really understand the
significance of Haskell functors for Haskell programmers, we [I?] need
to have a better understanding of how Haskell structural functions are
defined in Haskell?
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
