Re: [Haskell-cafe] Questions about the Functor class and it's use in "Data types à la carte"

[Philip Weaver]

On Dec 14, 2007 11:44 AM, Corey O'Connor <coreyoconnor at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071214/86547b32/attachment.htm