Functor for square matrices

Question

In my previous question here (Nested datatype for square matrices) a datatype Square has been introduced. Now I want to write a functor instance for it. So I begin with map functions for all the four types. I have managed to do so for Nil and Cons:

mapNil :: ((a -> b) -> a -> b) -> (Nil (a -> b) -> Nil a -> Nil b )
mapNil map f Nil = Nil


mapCons :: (forall b . ((a -> b) -> a -> b) -> (t (a -> b) -> t a -> t b))
        -> ((a -> b) -> a -> b)
        -> ((Cons t (a -> b)) -> Cons t a -> Cons t b)
mapCons mapT mapA (Cons f consf) (Cons x consx) =  Cons (mapA f x) (mapT mapA consf consx)

Now, the Square' type:

mapSquare' :: (forall b . ((a -> b) -> a -> b) -> (t (a -> b) -> t a -> t b))
           -> ((a -> b) -> a -> b)
           -> ((Square' t (a -> b)) -> Square' t a -> Square' t b)
mapSquare' mapT mapA (Zero fs) (Zero xs) = Zero (mapT (mapT mapA) fs xs) -- it is wrong
mapSquare' mapT mapA (Succ fs) (Succ xs) = mapSquare' (mapCons mapT) mapA fs xs

And then I will do something like this:

mapSquare = ...

-- this is, actually, the final goal:
instance Functor Square where
fmap = mapSquare

So far, for my mapSquare' Haskell says this:

• Occurs check: cannot construct the infinite type: a ~ t a
  Expected type: (a -> t b) -> a -> t b
    Actual type: t (a -> b) -> t a -> t b
• In the first argument of ‘mapT’, namely ‘(mapT mapA)’
  In the first argument of ‘Zero’, namely ‘(mapT (mapT mapA) fs xs)’
  In the expression: Zero (mapT (mapT mapA) fs xs)

My plan was that (mapT mapA) would "lift" it all between (t (t a)) and (t a) levels. What is my mistake? I would appreciate your help.

Answer 1

You can not use mapSquare since that type is too restrictive. A functor has type fmap :: Functor f => (c -> d) -> f c -> f d. But ((a -> b) -> a -> b) -> (Square (a -> b)) -> Square a -> Square b would only cover a subset of that. Your mapSquare' looks more like a "sequential application" (<*>) :: Applicative f => f (a -> b) -> f a -> f b. Notice that a (<*>) takes two f x items, not one, like the fmap does.

If you want to declare Square an instance of Functor, it is likely, depending on the way you implement it, that Nil and Const needs to be an instance of Functor as well. We can easily make these an instance of Functor:

instance Functor Nil where
    fmap _ Nil = Nil

instance Functor t => Functor (Cons t) where
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

Now we can make Square' an instance of Functor with:

instance Functor t => Functor (Square' t) where
    fmap f (Zero x) = Zero (fmap (fmap f) x)
    fmap f (Succ x) = Succ (fmap f x)

You actually do not generate those yourself. You can use the DeriveFunctor [ghc-doc] compiler option, and let the compiler derive the functions for you:

{-# LANGUAGE DeriveFunctor #-}

data Square' t a = Zero (t (t a) ) | Succ (Square' (Cons t) a) deriving Functor
data Nil a = Nil deriving Functor
data Cons t a = Cons a (t a) deriving Functor

This will construct the functors specified as here discussed.