haskellmonadstypeclassalternative-functorfoldable

Could it be that (Alternative f, Foldable f) => Monad f?

The following typechecks:

instance (Applicative f, Alternative f, Foldable f) => Monad f where 
  (>>=) = flip $ \f -> foldr (<|>) empty . fmap f
  -- Or equivalently
  a >>= b = getAlt . foldMap Alt . fmap b $ a

Is this actually a valid Monad instance? If yes, why is it not used? If no, does it break any laws or such? I have not proved that the laws hold, but I couldn't find a counterexample either.

Solution

  • This should be a counterexample to the right identity monad law.

    Below, we exploit the functor product Maybe :*: Maybe from GHC.Generics, but it could be inlined, if wished. This is also an applicative, alternative, foldable, and monad. I trust the libraries on these instances to be law-abiding.

    We then compare the proposed instance Monad (the one in the question) to the standard library one. We find that the right identity law is not satisfied for the proposed instance, while it appears to hold (at least in my very limited tests) in the library instance.

    {-# LANGUAGE FlexibleInstances, GeneralizedNewtypeDeriving, TypeOperators #-}
{-# OPTIONS -Wall #-}

module NotAMonad where

import Control.Applicative
import GHC.Generics ((:*:)(..))

-- A basic wrapper to avoid overlapping instances, and to be able to
-- define a custom monad instance.
newtype Wrap m a = Wrap { unWrap :: m a }
    deriving (Functor, Applicative, Alternative, Foldable, Show)

-- The proposed instance
instance (Applicative f, Alternative f, Foldable f) => Monad (Wrap f) where 
  (>>=) = flip $ \f -> foldr (<|>) empty . fmap f

-- This is Applicative, Alternative, and Foldable
type T = Maybe :*: Maybe

-- A basic test
test :: Wrap T Int
test = Wrap (Just 3 :*: Just 4) >>= return
-- result:
-- Wrap {unWrap = Just 3 :*: Just 3}

    The 4 is now replaced by 3. I have not tried to explain why, though. I guess it is caused by Just 3 <|> Just 4 = Just 3.

    Using the library monad instance, instead, everything looks fine:

    > (Just 3 :*: Just 4) >>= return
Just 3 :*: Just 4