神刀安全网

A functor is not a box

In this post I will go into why a functor is not a box, and why it is a bad idea to to explain functors as such. The ideas in this post extend beyond the problem of explaining functors, but functors will serve as a good example.

I have been thinking a lot about inaccuracies in teaching lately. I have come to the conclusion that inaccuracies may be required for a good explanation, but they have to be handled responsibly. In my opinion, inaccuracies should only be considered responsible if they approximate an accurate description of the real situation. That means that any explanation that is verifiably false should be considered irresponsible and must be avoided.

Boxes?

The most pungent example that came to my mind on this topic was how functors are usually explained as boxes. Functors are often explained as “A functor is a box”, or the slightly better “A functor is like a box”. Examples of this can be found here , here , here and here , but also here and here , here , here , here and some more here (and that’s just the first two pages of Google’s results for ‘A functor is a box.’).

I would like to address this as a didactic failure. I have only two ways of responsibly explaining the concept of a functor and they certainly do not include a box-analogy.

Functors

  1. In category theory: A functor is a mapping between categories that preserves the category structure.
  2. In Functional programming: A functor is a type constructor that instantiates the Functor type class and is implemented according to its laws.

For the purpose of this post, I will use the Haskell definition of a functor:

A Functor f is a unary type constructor (a type constructor of kind * -> * ) such that there exists a function fmap :: (a -> b) -> f a -> f b

class Functor f where   fmap :: (a -> b) -> f a -> f b 

… that satisfies these two laws:

fmap id  ==  id fmap (f . g)  ==  fmap f . fmap g

For the record, Google defines a box as follows:

box (noun) a container with a flat base and sides, typically square or rectangular and having a lid.

Boxes?

It is easy to see where the ‘box’ analogy comes from. If we define a data type Box as follows …

data Box a = Box a

…, then we can write a Functor instance for it:

instance Functor Box where   fmap f (Box a) = Box (f a)

It is easy to see that this definition conforms to the Functor laws:

fmap id (Box a)   = Box (id a)   = Box a   = id (Box a)  fmap (f . g) (Box a)   = Box ((f . g) a)   = Box (f (g a))   = fmap f (Box (g a))   = fmap f (fmap g (Box a))   = (fmap f . fmap g) (Box a)

So a box is a functor? Yes, if you define ‘box’ similarly, I never contradicted that.

You can also see how lists may be (possible very long) boxes or perhaps even how trees may be regarded as boxes with branches.

Definitely not boxes

Let’s look at some examples of functors that do not look like boxes:

First up: Const a :

data Const a b = Const a

Note that b in this definition is what’s called a phantom-type. It is a type variable but it is not used. It does make a difference though. It changes the kind of Box a from * to * -> * .

As such, Const a (for any fixed a , that is), is now a functor:

instance Functor (Const a) where   fmap _ = id

fmap for Const a ignores the given function and just applies the identity function to the value. This implementation satisfies the Functor laws…:

fmap id (Const a)   = Const a   = id (Const a)  fmap (f . g) (Const a)   = Const a   = fmap g (Const a)   = fmap f (fmap g (Const a))   = (fmap f . fmap g) (Const a)

…, but we can hardly say it’s a box. Well, that’s not entirely true, is it? You could say it’s an empty box attached to a value…

Note that this means that we can make any type a Functor by adding a phantom type variable.

Let’s look at another example instead of rambling about how attaching an empty box to a horse does not make the resulting entity a box.

Functions

You wouldn’t say a function in a givencorange r ( (->) r ) is a box, right? Nonetheless, (->) r is indeed a Functor :

instance Functor ((->) r) where   fmap = (.)

And indeed, this implementation satisfies the Functor laws:

fmap id fun   = id . fun   = fun   = id fun  fmap (f . g) fun   = f . g . fun   = fmap f (g . fun)   = fmap f (fmap g fun)   = (fmap f . fmap g) fun

If you don’t agree that a function is not a box, at least give me that it’s not cuboid-shaped nor has a lid.

Okay, maybe not a box but…

Sometimes we see other analogies like a ‘container’, which is only marginally better because we never used any box-specific properties of a box (like its cuboid shape) in what’s written above so we might as well have written ‘container’. ‘Mappable’ is also sometimes used, but as discussed in the Const a example, it is also only slightly better as any type can be made mappable by adding a phantom type variable. Of course you can still accurately call a Functor a box if you defined ‘box’ to mean ‘ Functor but then the point of the analogy breaks down.

Why boxes?

If Functor really doesn’t mean ‘box’, why do so many blog posts appear that say otherwise? This is speculation, but my guess is that the writers of these explanations want to explain the concept of a Functor such that readers who haven’t understood higher-kinded types and/or type classes may understand it as well. This is perhaps a noble endeavor, but I consider it harmful to the reader. By willfully writing erroneous explanations, they deny the reader good foundational knowledge of what a Functor really is.

It is essential that a beginner Haskell programmer figures out what type classes and type constructors are before learning what a Functor is. Similarly, you wouldn’t try to explain what a mammal is by saying ‘a mammal is a human’, even if you don’t want to explain where milk comes from.

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » A functor is not a box

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址