Hello,
I would like to propose to add a way to automatically derive instances
of Functor. From looking at existing code, it seems that almost all
Functor instances I see are derivable using the algorithm presented
here, resulting in less boilerplate code. This proposal is compatible
with Haskell98 (and therefore also with Haskell').
Let's start with an example. The following declaration:
> data Tree a = Leaf | Node (Tree a) a (Tree a)
> deriving Functor
would generate the following Functor instance:
> instance Functor Tree where
> fmap f (Leaf ) = Leaf
> fmap f (Node l a r) = Node (fmap f l) (f a) (fmap f r)
To be able to derive Functor in a general way, more classes are needed
to support functors over other parameters:
> class Functor2 f where fmap2 :: (a -> b) -> f a x -> f b x
> class Functor3 f where fmap3 :: (a -> b) -> f a x y -> f b x y
> -- etc.
Provided instances would be:
> instance Functor ((,) a) -- currently in Control.Monad.Instances
> instance Functor2 (,)
> instance Functor ((,,) a b)
> instance Functor2 ((,,) a)
> instance Functor3 (,,)
> instance Functor ((,,,) a b c)
> instance Functor2 ((,,,) a b)
> instance Functor3 ((,,,) a)
> instance Functor4 (,,,)
> -- etc.
Also, a contravariant functors can come up:
> class CoFunctor f where cofmap :: (a -> b) -> f b -> f a
> class CoFunctor2 f where cofmap2 :: (a -> b) -> f b x -> f a x
> -- etc.
Now, to derive functor for a data type
> data D a = C1 u v w | C2 x y z | ...
The instance would be:
> instance Functor D where
> fmap f d = case d of
> C1 q r s -> C1 (fmap_<a,u> f q) (fmap_<a,v> f r) (fmap_<a,w> f s)
> C2 t u v -> C1 (fmap_<a,x> f t) (fmap_<a,y> f u) (fmap_<a,z> f v)
> ...
With the appropriate context. Here fmap_<a,b> is the deriving scheme to
derive a functor over type b, parameterized by the type variable a:
> fmap_<a, a> f = f
> fmap_<a, b> f = id -- b does not contain a
> fmap_<a, T x> f = fmap (fmap_<a,x> f)
> fmap_<a, T x y> f = fmap2 (fmap_<a,x> f) . fmap (fmap_<a,y> f)
> --etc.
> fmap_<a, x -> y> f = \u -> fmap_<a, y> f . u . cofmap_<a, x> f
>
> cofmap_<a, b> f = id -- b does not contain a
> cofmap_<a, T x> f = cofmap (fmap_<a,x> f)
> cofmap_<a, T x y> f = cofmap2 (fmap_<a,x> f) . cofmap (fmap_<a,y> f)
> --etc.
> cofmap_<a, x -> y> f = \u -> cofmap_<a, y> f . u . fmap_<a, x> f
Before type checking to determine the required instances, the
transformations
fmapN id --> id
cofmapN id --> id
must be applied. Otherwise unnecessary instances will be required, see
the State example below.
Here are some examples of the deriving scheme. The derived instances are
exactly as you would expect:
> data Tree a = Leaf | Node (Tree a) a (Tree a)
The instance is derived as:
> fmap f d = case d of
> Leaf -> Leaf
> Node a b c -> Node (fmap_<a,Tree a> f a) (fmap_<a,a> f b)
> (fmap_<a,Tree a> f c)
> = Node (fmap (fmap_<a,a> f) a) (f b)
> (fmap (fmap_<a,a> f) c)
> = Node (fmap f a) (f b) (fmap f c)
It also works for things like monad transformers:
> newtype StateT s m a = StateT (s -> m (a, s))
> fmap f (StateT a) = StateT b
> where b = fmap_<a, s -> m (a, s)> f a
> = fmap_<a, m (a, s)> f . a . cofmap_<a, s> f
> = fmap_<a, m (a, s)> f . a . id
> = fmap (fmap_<a, (a, s)> f) . a
> = fmap (fmap2 (fmap_<a, a> f) . fmap (fmap_<a, s> f)) . a
> = fmap (fmap2 f . fmap id) . a
> = fmap (fmap2 f) . a
> = \s -> fmap (\(a,s) -> (f a, s)) (a s)
Even for Cont:
> newtype Cont r a = ContT ((a -> r) -> r)
> fmap f (ContT a) = ContT b
> where b = fmap_<a, (a -> r) -> r> f a
> = fmap_<a, r> f . a . cofmap_<a, a -> r> f
> = id . a . cofmap_<a, a -> r> f
> = a . (\u -> cofmap_<a, r> f . u . fmap_<a,a> f)
> = a . (\u -> id . u . f)
> = a . (. f)
There are some (minor) problems with this approach. First of all the
treatment of (->) is rather ad-hoc, consider:
> newtype Arrow a b = a -> b deriving (Functor, CoFunctor2)
> data A a = A (T a -> ()) deriving Functor
> data B a = B (Arrow (T a) ()) deriving Functor
In the first case the derived instance is:
> instance CoFunctor T => Functor A where
> fmap f (A u) = A (u . cofmap f)
While for the second type the following is derived:
> instance (Functor T, Functor2 Arrow) => Functor B where
> fmap f (B u) = fmap2 (fmap f)
Consider also:
> newtype Problem a = Problem (T (U a)) deriving Functor
Now there are two possible functor instances, depending on the instances
for T and U:
> instance Functor Problem where fmap f = fmap (fmap f)
> instance Functor Problem where fmap f = cofmap (cofmap f)
Currently the algorithm chooses the former, it will only use CoFunctor
if (->) is present, and it tries to get rid of it as soon as possible.
This also comes up when trying to derive an instance for this variation
of Cont:
> data C r a = C ((a -> r, a -> r) -> r) deriving Functor
Because it uses a type constructor in a contravariant position. The
derivation goes as follows:
> fmap f (C a) = C b
> where b = fmap_<a, (a -> r, a -> r) -> r>
> = fmap_<a, r> f . a . cofmap_<a, (a -> r, a -> r)> f
> = id . a . cofmap_<a, (a -> r, a -> r)> f
> = a . cofmap2 (fmap_<a, a->r> f) . cofmap (fmap_<a, a->r> f)
> = a . cofmap2 (fmap_<a, a->r> f)
> . cofmap (\u -> cofmap_<a, a> f . u . fmap_<a,r> f)
> = error, unable to realize: cofmap_<a,a>
The desired instance would be:
> ... = a . cofmap_<a, (a -> r, a -> r)> f
> = a . fmap2 (cofmap_<a, a -> r> f)
> . fmap (cofmap_<a, a -> r> f)
> = a . fmap2 (cofmap_<a, a -> r> f)
> . fmap (\u -> cofmap_<a,r> f . u . fmap_<a, a> f)
> = a . fmap2 (cofmap_<a, a -> r> f) . fmap (.f)
> = a . fmap2 (.f) . fmap (.f)
> = \(x,y) -> a . (x . f, y . f)
However, I highly doubt this problem will come up in practice. A
'solution' would be to replace:
> cofmap_<a, T x y> f = cofmap2 (fmap_<a,x> f) . cofmap (fmap_<a,y> f)
with
> cofmap_<a, T x y> f = fmap2 (cofmap_<a,x> f) . fmap (cofmap_<a,y> f)
Thereby removing all uses of CoFunctor. Maybe that would be a better
definition?
Finally, if Data.Foldable and Data.Traversable are added to the
standard, they could be derived in a similair way.
Twan van Laarhoven
_______________________________________________
Haskell-prime mailing list
Haskell-prime@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-prime
