On Dec 14, 2007 11:44 AM, Corey O'Connor <coreyoconnor@gmail.com> wrote:

I'm working through the interesting paper "Data type à la carte" and
am confused by the Functor instance for Val. I think this stems from
some confusion of mine regarding the Functor class in general.

I'll try to explain, but I might not be very clear :).

The Functor instance I'm confused about is:
instance Functor Val where
fmap f (Val x ) = Val x

where Val is defined as:
data Val e = Val Int

Is this the only valid Functor instance for the Val type? Even though
I'd, naively, expect the Functor instance to look like:
instance Functor Val where
fmap f (Val x) = Val (f x)

Yes, I think people often expect this, because they're used to the idea that fmap applies a function to all the terminal elements in a data structure. For example, if you map a function across a list or tree, you expect the function to be applied to each value or node, not the branches themselves, and to preserve the structure of the tree or list. This is not the case when you use functors as you are in your email (I think sometimes called "syntactic functors", for traversing abstract syntax trees); In this case, you are only pushing the function into all recursive subterms of a data structure, which the function then operates on.

So, consider this data structure:

   data Val e = Add e e
                   | Val Int

   instance Functor Val where
       fmap f (Val x) = Val x
       fmap f (Add x y) = Add (f x) (f y)

Notice that it is not (fmap f x) and (fmap f y). You only push the function one level deeper, not all the way down (the catamorphism takes care of fmap-ing the function all the way down).

I suspect that would not work out due to the type of the Val
constructor. Is this correct?

Correct, the types wouldn't work. Try it and see :)

The reason I find all this odd is because I'm not sure how the type
class Functor relates to the category theory concept of a functor. How
does declaring a type constructor to be an instance of the Functor
class relate to a functor? Is the type constructor considered a
functor?

I could try to answer this one, but I would just confuse both of us, heh. Hope I was helpful!

Any help would be, of course, greatly appreciated.

-Corey O'Connor
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe