{"id":711,"date":"2016-01-01T21:00:06","date_gmt":"2016-01-01T21:00:06","guid":{"rendered":"http:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/?p=711"},"modified":"2017-03-04T06:22:43","modified_gmt":"2017-03-04T06:22:43","slug":"insights-into-why-a-contravariant-type-cant-be-a-haskell-functor","status":"publish","type":"post","link":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/?p=711","title":{"rendered":"Insights into why a contravariant type can\u2019t be a Haskell Functor"},"content":{"rendered":"

In learning Haskell’s core types, type classes, and concepts, one often finds counterexamples useful in learning what these abstract concepts “really are”. Perhaps one of the most well-understood type class hierarchies is Functor-Applicative-Monad<\/code>. We encounter Functor<\/code> in the context of things that are “mappable”. It’s a producer, and using fmap<\/code> we can “post-transform” all of the things that it produces in a way that preserves any underlying structure.<\/p>\n

We quickly become familiar with a number of useful functors, like Maybe<\/code>, []<\/code>, (->) r<\/code>, IO<\/code>. Functors seem to be everywhere. So, then, one asks, what might be a parameterized type that’s not<\/em> a functor? The go-to example is something that’s contravariant in its type parameter, like a -> Int<\/code>, as a type-level function of parameter a<\/code>. There doesn’t seem to be any useful<\/em> way to make it a Functor<\/code> in a<\/code>. That said, seemingly “useless” type-level artifacts are often quite useful, like the Const Functor<\/code>, defined as Const r a ~= r<\/code> (the a<\/code> is a phantom type and functions being fmap<\/code>ed are ignored). So usefulness in this world isn’t always intuitive. Still, it remains true that something like a -> Int<\/code> is not<\/em> a functor? Why?<\/p>\n

Let’s work with the type a -> Bool<\/code>, just because it’s the simplest example of what goes wrong. Is there a way to make a Functor<\/code> instance for that? To me, it’s not intuitive that that thing isn’t a Functor<\/code>. It’s “almost” a set (stepping around, for a moment, debates about what is a set) and Set<\/code>, meaning the actual collection type in Data.Set<\/code> is “almost” a Functor<\/code>. It’s not one, because a Functor<\/code> demands that the mapping be structure-preserving, which a set’s notion of mapping is not (for example, if you map the squaring function on the set {2, -2}, you get a smaller set, {4}). There are many ways to get at the point that Set<\/code> is not a Functor<\/code>, most relying on the fact that Set a<\/code>‘s methods almost invariably require Eq a<\/code> and Ord a<\/code>. But what about the type-agnostic “(<-) a<\/code>” (my notation) above? It places no such constraints on a<\/code>.<\/p>\n

To answer this, let’s try to create the method, fmap<\/code>, on which Functor<\/code> relies.<\/p>\n

\n


\n-- pretend Haskell supports (<-) b a as a syntax for (->) a b = a -> b<\/code><\/p>\n

instance Functor (<-) Bool where<\/code><\/p>\n

-- fmap :: (a -> b) -> f a -> f b<\/code>
\n-- in this case, (a -> b) -> (a -> Bool) -> (b -> Bool)<\/code>
\nfmap f x = ??<\/code><\/p>\n<\/blockquote>\n

The type signature that we’re demanding of our fmap<\/code> is an interesting one: (a -> b) -> (a -> Bool) -> (b -> Bool)<\/code>. Notice that such a function doesn’t have any a<\/code> to work with. One might not exist: the Functor<\/code> needs to be valid over empty types (e.g. Void<\/code>; note that [Void]<\/code> is not empty but has exactly one element, []<\/code>). In typical Functor<\/code> cases, the a = Void<\/code> case is handled soundly. For example, consider the list case: ([] :: [Void]<\/code> maps to [] :: [b]<\/code> for any b<\/code>), and any non-empty list has a<\/code>s to work with. In this case, fmap<\/code>‘s type signature gives us two things that we can do with a<\/code>‘s but no a<\/code>. This means that we have to ignore the first two arguments; we can’t use them.<\/p>\n

instance Functor (<-) Bool where<\/code><\/p>\n

-- fmap :: (a -> b) -> f a -> f b<\/code>
\n-- in this case, (a -> b) -> (a -> Bool) -> (b -> Bool)<\/code>
\nfmap _ _ = (?? :: b -> Bool)<\/code><\/p>\n

This rules out any useful<\/em> Functor<\/code>s. In fact, our need for an expression that inhabits b -> Bool<\/code> for any b<\/code> limits us to two non-pathological possibilities: the constant functions! Since we don’t have any b<\/code> to work with, either, we have to commit to one of those.\u00a0Without loss of generality<\/a>, I’m going to use the definition fmap _ _ = const True<\/code>. With a few tweaks to what I’ve done, Haskell will actually allow such a “Functor<\/code>” instance to be created. But will it be right<\/em>? It turns out that it won’t be. To show this, we consult the laws for the Functor<\/code> type class. In fact, we only need the simplest one (Identity): fmap id === id\u00a0<\/code>to refute this one. That law is violated by the constant “Functor<\/code>” above:<\/p>\n

fmap id (const True) = const True -- OK!<\/code>
\nfmap id (const False) = const True -- whoops!<\/code><\/p>\n

So it turns out that (<-) Bool<\/code> (my notation) has no<\/em> Functor<\/code> instances at all (the only properly polymorphic candidate fails the type class’s most basic law) and the more complicated cases fail similarly.<\/p>\n

\"\"<\/a> \"\"<\/p>\n","protected":false},"excerpt":{"rendered":"

In learning Haskell’s core types, type classes, and concepts, one often finds counterexamples useful in learning what these abstract concepts “really are”. Perhaps one of the most well-understood type class hierarchies is Functor-Applicative-Monad. We encounter Functor in the context of things that are “mappable”. It’s a producer, and using fmap we can “post-transform” all of […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18],"tags":[],"class_list":["post-711","post","type-post","status-publish","format-standard","hentry","category-jan-2016"],"_links":{"self":[{"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=\/wp\/v2\/posts\/711","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=711"}],"version-history":[{"count":1,"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=\/wp\/v2\/posts\/711\/revisions"}],"predecessor-version":[{"id":712,"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=\/wp\/v2\/posts\/711\/revisions\/712"}],"wp:attachment":[{"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=711"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=711"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sasamat.xen.prgmr.com\/michaelochurch\/wp\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=711"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}