Czy to możliwe (Alternatywne f, Składane f) => Monad f?

Question

Poniższe 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 

Czy to rzeczywiście ważny instancja Monad? Jeśli tak, dlaczego nie jest używany? Jeśli nie, czy łamie jakiekolwiek prawa lub takie? Nie udowodniłem, że prawa istnieją, ale nie mogłem też znaleźć kontrprzykładu.

Answer 1

To powinien być kontrprzykład w prawo prawa monady tożsamości.

Poniżej, wykorzystujemy funktor produktu Maybe :*: Maybe z GHC.Generics, ale może być wskazany, jeśli chcesz. Jest to również aplikacja, alternatywa, składana i monada. Ufam, że biblioteki w tych przypadkach są zgodne z prawem.

Następnie porównujemy proponowaną instance Monad (tę w pytaniu) do standardowej biblioteki. Uważamy, że prawo właściwe dla tożsamości nie jest spełnione dla proponowanej instancji, podczas gdy wydaje się, że ma ona miejsce (przynajmniej w moich bardzo ograniczonych testach) w instancji biblioteki.

{-# 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 jest teraz zastąpiony przez 3. Jednak nie próbowałem wytłumaczyć, dlaczego. Przypuszczam, że jest to spowodowane przez Just 3 <|> Just 4 = Just 3.

Korzystanie instancję monada biblioteki, zamiast, wszystko wygląda dobrze:

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

Answer 2

Alternative jest trochę hacky bestii. Zasadniczo jest to klasa monofonicznych konstruktorów : typowych T takich, że dla dowolnego zawartego typu jest monoidem. To nie ma wiele wspólnego z funktorami ... monadami i jest znacznie mniej matematycznie głębokie. (Tak, tylko dla matematycznej elegancji, byłoby nieco źle ustawiony Monad pod Alternative).

Napiszmy, że wystąpienie w kategoriach Monoid dla jasności (nie będzie faktycznie kompilacji):

instance (Foldable f, (∀ x . Monoid (f x))) => Monad f where 
    (>>=) = flip $ \f -> foldr mappend empty . fmap f 
     ≡ flip $ \f -> fold . fmap f 
     ≡ flip foldMap 

lub rzeczywiście

to zdecydowanie nie jest coś nieznanego.

Aby sprawdzić przepisy ustawowe, mamy najlepszy wygląd w formułowaniu Kleisli:

(f <=< g) x = f =<< g x 
       ≡ foldMap f $ g x 

tj

f <=< g = foldMap f . g 

Następnie ustaw Monad są

• Lewy tożsamość

  f <=< pure ≡ foldMap f . pure =! f 
  

• Prawy tożsamość

  pure <=< f ≡ foldMap pure . f =! f 
  

• Łączność

  (f <=< g) <=< h ≡ foldMap (foldMap f . g) . h 
         =! foldMap f . foldMap g . h 
         ≡ foldMap f . (foldMap g . h) ≡ f <=< (g <=< h) 
  

Tak w skrócie, musimy

• foldMap f . pure =! f =! foldMap pure . f ∀ f
• foldMap (foldMap f . g) =! foldMap f . foldMap g ∀ f, g

To na pewno nie wygląda nierozsądne, ale nie widzę skąd można rygorystycznie zawrzeć to dla arbitralnego Foldable + Alternative wystąpień.

Naprawdę, dużym problemem, jaki widzę w tym przypadku, jest to, że nie jest on wystarczająco ogólny. Większość monad nie jest ani Foldable ani Alternative. Jeśli istniała definicja typu "cover-all", taka jak ta, którą proponujesz, wymagałaby ona zdefiniowania dowolnej instancji na poziomie OverlappingInstances, a te są ogólnie uważane za coś, czego nie powinieneś używać bez uzasadnionego powodu.

Zastanawiam się jednak, czy nie byłoby żadnych problemów z domyślnej definicji dla metody wiązania po :

{-# LANGUAGE DefaultSignatures #-} 
class Applicative f => Monad f where 
    return :: a -> m a 
    return = pure 
    (>>=) :: m a -> (a -> m b) -> m b 
    default (>>=) :: (Foldable m, Monoid m b) 
      => m a -> (a -> m b) -> m b 
    (>>=) = flip foldMap 

To by przynajmniej umożliwić zdefiniowanie np instancja lista prostu jako

instance Monad [] 

bez konieczności wypisać metody w ogóle, ponieważ na pewno wystarczy, foldMap ≡ concatMap ≡ (=<<).