Pourquoi est-ce que j'obtiens une erreur "chevauchement d'instances" lorsque l'une ne correspond pas?

Question

J'essaye de permettre l'incorporation d'une monade d'état dans ma monade libre; voici ma tentative simple,:

{-# language FlexibleInstances, MultiParamTypeClasses #-} 
module Main where 

import Control.Monad.Free 
import Control.Monad.State 
import Data.Bifunctor 

data Toy state next = 
     Output String next 
    | LiftState (state -> (next, state)) 
    | Done 

instance Functor (Toy s) where 
    fmap f (Output str next) = Output str $ f next 
    fmap f (LiftState stateF) = LiftState (first f . stateF) 
    fmap f Done = Done 

instance MonadState s (Free (Toy s)) where 
    state = overState 

overState :: (s -> (a, s)) -> Free (Toy s) a 
overState = liftF . LiftState 

output :: Show a => a -> Free (Toy s)() 
output x = liftF $ Output (show x)() 

done :: Free (Toy s) r 
done = liftF Done 

program :: Free (Toy Int)() 
program = do 
    start <- get 
    output start 
    modify ((+10) :: (Int -> Int)) 
    end <- get 
    output end 
    done 

interpret :: (Show r) => Free (Toy s) r -> s -> IO() 
interpret (Free (LiftState stateF)) s = let (next, newS) = stateF s 
             in interpret next newS 
interpret (Free (Output str next)) s = print str >> interpret next s 
interpret (Free Done) s = return() 
interpret (Pure x) s = print x 

main :: IO() 
main = interpret program (5 :: Int) 

Je reçois l'erreur:

• Overlapping instances for MonadState Int (Free (Toy Int)) 
    arising from a use of ‘get’ 
    Matching instances: 
    instance [safe] (Functor m, MonadState s m) => 
        MonadState s (Free m) 
     -- Defined in ‘Control.Monad.Free’ 
    instance MonadState s (Free (Toy s)) 
     -- Defined at app/Main.hs:18:10 
• In a stmt of a 'do' block: start <- get 
    In the expression: 
    do { start <- get; 
     output start; 
     modify ((+ 10) :: Int -> Int); 
     end <- get; 
     .... } 
    In an equation for ‘program’: 
     program 
     = do { start <- get; 
       output start; 
       modify ((+ 10) :: Int -> Int); 
       .... } 

Pour autant que je peux rassembler; il essaie d'appliquer cette instance:

(Functor m, MonadState s m) => MonadState s (Free m) 

du free package here; Cependant, dans ce cas, il devrait correspondre Free (Toy s) et il n'y a pas MonadState s (Toy s) comme requis, donc je ne comprends pas pourquoi il pense que cela s'applique.

Si je retire ma définition d'exemple, je reçois:

• No instance for (MonadState Int (Toy Int)) 
    arising from a use of ‘modify’ 

qui soutient ma pensée que l'autre instance ne s'applique pas réellement; Comment puis-je obtenir ceci pour compiler en utilisant mon instance spécifiée? Et pouvez-vous expliquer pourquoi cela se produit? Est-ce dû à l'utilisation de FlexibleInstances?

Merci!

Answer 1

Le contexte d'instance (le bit (Functor m, MonadState s m)) est simplement ignoré lors du choix des instances. Ceci afin d'éviter que le compilateur doive effectuer une recherche backtracking potentiellement coûteuse pour choisir une instance. Donc, si deux instances s'appliquent et qu'une seule est exclue à cause d'un contexte d'instance, comme dans votre cas, c'est un chevauchement.

Ceci est une partie malheureuse de la conception de mtl, et je pense que chaque programmeur Haskell s'est heurté à un moment ou un autre. Il n'y a pas beaucoup de choix pour les corrections; généralement vous ajoutez un newtype et donnez votre instance, comme dans

newtype FreeToy s a = FreeToy (Free (Toy s) a) 
instance MonadState s (FreeToy s) where -- ...