A Type for Almost Functors

Sometimes you have a type you want to be a functor but, for whatever reason, it can’t be.

As a concrete example, consider a type representing some future value yet to be computed. I first encountered this when playing with a material system for a ray tracer. In this system there were a small number of material “types” which could be evaluated using some “light parameters” to produce a color output.

-- Different "types" of material
data Material = Shadeless Color
              | Diffuse Color

-- Evaluate a material to produce a color value
evaluateMaterial :: Material -> LightParams -> Color

In this example, Shadeless represents a material which emits a constant color value, unaffected by LightParams. Diffuse represents a material which reflects light equally in all directions.

I wanted to increase the flexibility of the system by allowing for arbitrary computation in these material definitions. What if we parameterise Material by some type and make it a functor? The problem is that while Shadeless materials are essentially trivial containers for a Color (but could effectively be any type), Diffuse materials used their Color to generate a reflected Color based on LightParams when evaluated later. Here’s what I came up with:

data Material a = Constant a  -- Renamed to reflect its more general utility
                | Diffuse Color (Color -> a)

-- Constructs a constant color material
shadeless :: Color -> Material Color
shadeless = Constant

diffuse :: Color -> Material Color
diffuse c = Diffuse c id

evaluateMaterial :: Material a -> LightParams -> a

instance Functor Material where
	fmap f (Constant a) = Constant (f a)
	fmap f (Diffuse c g) = Diffuse c (f . g)

Since a Diffuse material can only be evaluated to a color, in order to make it a functor, it now carries an additional function which will be applied the the eventual output when it’s calculated. The fmap implementation can just compose the two functions together. We are effectively delaying the effect of fmap until we have the Color value to feed the function.

This works just fine, but if we start adding additional material types (e.g. mirror) we have to repeat the same pattern:

data Material a = Constant a 
                | Diffuse Color (Color -> a)
                | Mirror (Color -> a)

Can we do better and avoid this repetition?

Generalization

We can factor-out the notion of carrying-around a function to apply later into a new constructor. This version uses GADTs so the Diffuse and Mirror constructors can only have type Material Color:

data Material where
	Constant :: a -> Material a
	Diffuse :: Color -> Material Color
	Mirror :: Material Color
	App :: (a -> b) -> Material a -> Material b
	
instance Functor Material where
	fmap f (Constant a) = Constant (f a)
	fmap f (App g m) = App (f . g) m
	fmap f m = App f m

If we fmap a Diffuse or Mirror material we can wrap it in an App. When we fmap an App we can just compose the functions as before.

This is definitely an improvement for adding more material types, but can we extract this pattern of a “delayed fmap” into something re-usable in other situations?

data DelayedFmap where
	DelayedFmap :: (b -> a) -> f b -> DelayedFmap f a
	
instance Functor (DelayedFmap f) where
	fmap f (DelayedFmap g x) = DelayedFmap (f . g) x
	
lift :: f a -> DelayedFmap f a
lift = DelayedFmap id
	
data MaterialT where
	Constant :: a -> Material a
	Diffuse :: Color -> Material Color
	Mirror :: Material Color

type Material a = DelayedFmap MaterialT a

shadeless :: Color -> Material Color
shadeless = lift . Constant

diffuse :: Color -> Material Color
diffuse = lift . Diffuse

mirror :: Material Color
mirror = lift Mirror

As is the case with most useful, sufficiently polymorphic types, we have not invented anything new here. It just so happens that this is exactly the definition of Coyoneda from the kan-extenions package on Hackage.

data Coyoneda where
	Coyoneda :: (b -> a) -> f b -> Coyoneda f a
	
liftCoyoneda :: f a -> Coyoneda f a
liftCoyoneda = Coyoneda id

type Material a = Coyoneda MaterialT a

The underlying theory and origins of this type are out of scope here (others have done a better job than I will) but suffice it to say that Coyoneda is the “free functor” in the sense that it provides just enough additional structure to make any Coyoneda f a functor in the most trivial way (by carrying around a function to apply later.) This makes it a really useful type to know about, for when you really want a type to be a functor, but it isn’t.

Generalization#

Generalization