<br><div class="gmail_quote">On Dec 14, 2007 11:44 AM, Corey O'Connor <<a href="mailto:coreyoconnor@gmail.com" target="_blank">coreyoconnor@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I'm working through the interesting paper "Data type à la carte" and<br>am confused by the Functor instance for Val. I think this stems from<br>some confusion of mine regarding the Functor class in general.
<br>
</blockquote><div><br>I'll try to explain, but I might not be very clear :).<br> <br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>The Functor instance I'm confused about is:<br> instance Functor Val where<br> fmap f (Val x ) = Val x <br></blockquote><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>where Val is defined as:<br> data Val e = Val Int<br><br>Is this the only valid Functor instance for the Val type? Even though<br>I'd, naively, expect the Functor instance to look like:<br> instance Functor Val where
<br> fmap f (Val x) = Val (f x)<br></blockquote><div><br>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.
<br><br>So, consider this data structure:<br><br> data Val e = Add e e <br> | Val Int<br><br> instance Functor Val where<br> fmap f (Val x) = Val x<br> fmap f (Add x y) = Add (f x) (f y)<br>
<br>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).<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>I suspect that would not work out due to the type of the Val
<br>constructor. Is this correct?</blockquote><div><br>Correct, the types wouldn't work. Try it and see :)<br> <br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br><br>The reason I find all this odd is because I'm not sure how the type<br>class Functor relates to the category theory concept of a functor. How<br>does declaring a type constructor to be an instance of the Functor
<br>class relate to a functor? Is the type constructor considered a<br>functor?<br></blockquote><div><br>I could try to answer this one, but I would just confuse both of us, heh. Hope I was helpful!<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>Any help would be, of course, greatly appreciated.<br><font color="#888888"><br>-Corey O'Connor<br>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org" target="_blank">
Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></font></blockquote></div><br>