I'm attempting to define a functor instance for datatype Terms, which looks like:

data Terms a = Var a | App (Terms a) (Terms a) | Abs (Terms (Maybe a)) 
                     | Const Integer | Add (Terms a) (Terms a) 
                     | IfZero (Terms a) (Terms a) (Terms a) | Y
deriving (Show,Eq)

However, I'm having trouble with the case for Abs.

My definition currently looks like this:

instance Functor Terms where
    fmap f (Var x) = Var (f x)
    fmap f (App t1 t2) = App (fmap f t1) (fmap f t2)
    fmap f (Abs t) = Abs (fmap f t)
    fmap f (Const n) = Const n
    fmap f (Add t1 t2) = Add (fmap f t1) (fmap f t2)
    fmap f (IfZero t1 t2 t3) = IfZero (fmap f t1) (fmap f t2) (fmap f t3)
    fmap f Y = Y

I've tried several different things to get around the Maybe in order to apply the function to the term, but there's just something I'm not quite getting. I know the Maybe type is a functor on its own which means that fmap should work on it automatically, I'm just not sure how to work around the fact that it can't return as a Maybe.

CodePudding user response：

The error comes from this line:

fmap f (Abs t) = Abs (fmap f t)

Abs contains a Maybe (Term a), and you want to get a Maybe (Term b), but f is of type a -> b. So, when you try to fmap it, you're passing a Term a to a function that takes in a. Clearly this doesn't work. Instead, make a Term a -> Term b with fmap f, then fmap that (creating a double fmap):

fmap f (Abs t) = Abs (fmap (fmap f) t)

CodePudding user response：

Yes Maybe is a functor on its own and thus it has its own fmap:

    fmap f (Abs t) = Abs (fmap₁ (fmap₂ f) t)

-- t               :: Terms (Maybe a)
--              f  ::              a  ->              b
--        fmap₂ f  ::        Maybe a  ->        Maybe b
-- fmap₁ (fmap₂ f) :: Terms (Maybe a) -> Terms (Maybe b)

The subscript indices are not part of the code and are there for illustrative purposes only. Or we could use TypeApplications to distinguish them:

*Main> :set -XTypeApplications
*Main> fmap @Maybe ( 1) $ Just 7
Just 8
*Main> fmap @Terms ( 1) $ Abs $ Var $ Just 8
Abs (Var (Just 9))

but there's no need for them here and plain fmaps work as well -- Haskell knows which to apply, according to the argument's type:

*Main> fmap ( 1) $ Just 7
Just 8
*Main> fmap ( 1) $ Abs $ Var $ Just 8
Abs (Var (Just 9))

CodePudding user response：

Another option is to move the composition structure into a datatype by turning Terms (Maybe a) into Scoped Terms a. Your Functor Terms instance stays the same.

Instead composition happens in Functor (Scoped exp), derived via the composition of exp and Maybe (Compose exp Maybe). This is how fmap = fmap . fmap is derived (modulo newtype wrapping).

{-# Language DerivingVia #-}

type    Scoped :: (Type -> Type) -> (Type -> Type)
newtype Scoped exp a = Scoped (exp (Maybe a))
  deriving (Functor, Applicative, Alternative, Foldable, Arbitrary1, ..)
  via Compose exp Maybe

This is the approach taken by Edward Kmett's bound library.

Bound.Scope.Scope:

type    Scope :: Type -> (Type -> Type) -> (Type -> Type)
newtype Scope bound exp free = Scope (exp (Var bound (exp free)))

Bound.Scope.Simple.Scope:

type    Scope :: Type -> (Type -> Type) -> (Type -> Type)
newtype Scope bound exp free = Scope (exp (Var bound free))

where Var = Either:

type Var :: Type -> Type -> Type
data Var bound free
  = B bound -- this is a bound variable
  | F free  -- this is a free variable