MonadFix :+: instance for GHC Generics
Motivation
I was reading Control.Monad.Fix in base and noticed that there was no instance for :+:
. But there are instances for several concrete sum types like Maybe, Either, and [], so there doesn't seem to be a reason to omit it.
Proposal
As noted in Erkok's thesis, Remark 2.6.4, for any monad based on a sum type, f of bottom determines the top level structure of mfix f
. Erkok in fact provides an alternative MonadFix Maybe
instance based on pattern-matching f undefined
(eqn 4.3). My proposed instance for :+: is thus along the same lines:
instance (MonadFix f, MonadFix g) => MonadFix (f :+: g) where
mfix f = case f undefined of
L1 _ -> L1 $ mfix (\x -> case f x of L1 y -> y)
R1 _ -> R1 $ mfix (\x -> case f x of R1 y -> y)
There doesn't seem to be a testsuite for MonadFix but a few examples show that my instance works similarly to the existing instances:
f, f2, f3 :: [Integer] -> Maybe [Integer]
f = const Nothing
f2 = \x -> Just (take 100 (1:x))
f3 = Just
test f = mfix f == to1 (mfix (from1 . f))
main = print [test f, test f2, test f3] -- [True,True,<infinite loop>]
It was a little tricky to test it due to the Monad
constraint on MonadFix. Perhaps the difficulty arises from deciding how to implement pure
for :+:
? I think most people would be happy with an instance that was right-biased like Either, pure = R1 pure
. Or the instance could have a constraint instance (MonadFix f, MonadFix g, Monad (f :+: g)) => MonadFix (f :+: g)
with UndecidableInstances
and leave it to the user to write an instance.