Recherche de critiques constructives sur l'implémentation des monades

Question

J'apprends les monades, c'est mon premier travail (à part la monade triviale). N'hésitez pas à critiquer impitoyablement tout ce qui s'y trouve. Je suis particulièrement intéressé par les réponses du type "plus idiomatique" et "plus élégant".

Cette monade compte le nombre de liaisons effectuées.

data C a = C {value :: a, count :: Int} deriving (Show)

instance Monad C where
    (>>=) (C x c) f = C (value $ f x) (c + 1)
    return x = C x 0

add :: (Num a) => a -> a -> C a
add x y = return $ x + y

-- Simpler way to do this? foldM is obviously something different.
mysum [x] = return x
mysum (x:xs) = mysum xs >>= add x

Answer 1

Stylistiquement, c'est très bien. Dans le monde réel, je m'attendrais à ce qu'il y ait 60 % de chances que cette notation soit utilisée au lieu de celle que vous avez donnée :

C x c >>= f = C (value $ f x) (c + 1)

Mais c'est tellement mineur que cela ne vaut guère la peine d'être mentionné.

Sur une note plus sérieuse, non pas stylistique mais sémantique : ce n'est pas une monade. En fait, il viole les trois lois des monades.

(1) return x >>= f  =  f x
(2) m >>= return    = m
(3) m >>= (f >=> g) = (m >>= f) >>= g

(Où (>=>) est défini comme suit f >=> g = \x -> f x >>= g . Si (>>=) est considéré comme un opérateur "d'application", alors (>=>) est l'opérateur de composition correspondant. J'aime énoncer la troisième loi en utilisant cet opérateur car il fait ressortir la signification de la troisième loi : l'associativité).

Avec ces calculs :

(1) :

return 0 >>= return 
  = C 0 0 >>= return
  = C (value $ return 0) 1
  = C 0 1
Not equal to return 0 = C 0 0

(2) :

C 0 2 >>= return
  = C (value $ return 0) 3
  = C 0 3
Not equal to C 0 2

(3)

C 0 0 >>= (return >=> return)
  = C (value $ (return >=> return) 0) 1
  = C (value $ return 0 >>= return) 1
  = C (value $ C 0 1) 1
  = C 0 1

Is not equal to:

(C 0 0 >>= return) >>= return
  = C (value $ return 0) 1 >>= return
  = C 0 1 >>= return
  = C (value $ return 0) 2
  = C 0 2

Il ne s'agit pas seulement d'une erreur dans votre implémentation. Il n'existe pas de monade qui "compte le nombre de liaisons". Il s'agit de doit violent les lois (1) et (2). Le fait que le vôtre viole la loi (3) est une erreur d'implémentation, cependant.

Le problème est que f dans la définition de (>>=) peut retourner une action qui a plus d'un lien, et vous l'ignorez. Vous devez ajouter le nombre de liaisons à partir des arguments de gauche et de droite :

C x c >>= f = C y (c+c'+1)
   where
   C y c' = f x

Cela permettra de compter correctement le nombre de liaisons et de satisfaire à la troisième loi, qui est la loi d'associativité. Elle ne satisfera pas les deux autres. Cependant, si vous laissez tomber le +1 de cette définition, alors vous faire obtenir une monade réelle, qui est équivalente à la Writer sur les + monoïde. Il s'agit essentiellement d'additionner les résultats de tous les sous-calculs. Vous pouvez l'utiliser pour compter le nombre de quelque chose mais pas de bind - bind est trop spécial pour être compté. Mais, par exemple :

tick :: C ()
tick = C () 1

Puis C comptera le nombre de tick qui se sont produits dans le calcul.

En fait, vous pouvez remplacer Int avec n'importe quel type et (+) avec n'importe quel associatif et obtenir une monade. C'est ce qu'un Writer monade est en général. Si l'opérateur n'est pas associatif, la troisième loi ne s'appliquera pas (vous voyez pourquoi ?).