Search code examples
haskellalternative-functor

Is it possible to write an Alternative instance for Identity a if there's a Monoid for a?

I'd like to write an Alternative instance for the Identity newtype. The skeleton isn't hard:

instance Alternative Identity where
  empty = _
  (<|>) = _

However, the implementation is impossible for all types. It would be easy if I have a Monoid instance for a though:

instance Alternative Identity where
  empty = Identity mempty
  (Identity a) <|> (Identity a') = Identity (a <> a')

Is there a way to tell the compiler that I want to define the Alternative instance only for when the type inside has a Monoid instance? Since the a isn't mentioned anywhere, I can't just use a constraint Monoid a =>.

Solution

  • An Alternative must provide empty for all types a, with no restrictions. Otherwise, it does not fulfill the Alternative contract.

    That is, if we have an instance Alternative f, we must have

    empty :: forall a . f a

    without any further constraints.

    Hence, Identity is not an Alternative.

    This is a known problem, found in many similar type classes. For instance, many would enjoy a Functor Set instance, but that would require

    fmap :: (a -> b) -> Set a -> Set b

    for all types a and b, while the function above can only be achieved on Ord types. Since we can't add the constraint, we do not get a functor.

    Still, one can try using a more general type class that accounts for additional constraints. Maybe something like

    class CFunctor c f where
   fmap :: (c a, c b) => (a->b) -> f a -> f b

class CFunctor c f => CApplicative c f where
   empty :: c a => f a
   (<*>) :: (c a, c b, c (a->b)) => f (a->b) -> f a -> f b

    but these are not the "standard" ones in the library. (I guess on hackage there should be something similar to the constrained class variants above.)