Buscando crítica constructiva en la implementación de la mónada

Question

Estoy aprendiendo mónadas, esta es mi primera experiencia laboral (aparte de la mónada trivial). Siéntete libre de criticar todo sin piedad. Estoy especialmente interesado en el tipo de respuestas "más idiomáticas" y "más elegantes".

Esta mónada cuenta el número de enlaces realizados.

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

Estilísticamente esto es muy agradable. En el mundo real, que sería de esperar una probabilidad del 60% de esta notación en lugar de la que diste:

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

Pero eso es tan insignificante que no vale la pena mencionar.

En una nota más seria, no estilística sino semántica: esto no es una mónada. De hecho, viola las tres leyes de la mónada.

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

(Donde (>=>) se define como f >=> g = \x -> f x >>= g. Si (>>=) se considera un operador "aplicación", a continuación, (>=>) es el correspondiente operador de composición. Me gusta afirmar la tercera ley el uso de este operador, ya que pone de manifiesto la tercera ley de que significa: asociatividad)

Con estos cálculos:.

(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 0 >>= return 
    = C (value $ return 0) 1 
    = C 0 1 
Not equal to C 0 0 

(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 

Esto no es sólo un error en su aplicación - no hay una mónada que "cuenta el número de la liga". Es debe violar las leyes (1) y (2). Sin embargo, el hecho de que el suyo viole la ley (3) es un error de implementación.

El problema es que f en la definición de (>>=) puede devolver una acción que tiene más de un enlace, y usted está ignorando eso. Es necesario añadir a el número de la liga de los argumentos de izquierda y derecha:

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

Esto contar correctamente el número de la liga, y satisfarán la tercera ley, que es la ley asociatividad. No satisfará a los otros dos. Sin embargo, si suelta el +1 de esta definición, entonces do obtiene una mónada real, que es equivalente a la mónada Writer sobre el monoid +. Esto básicamente suma los resultados de todas las subcomputaciones. Puede usar esto para contar el número de algo, simplemente no se une, el enlace es demasiado especial para contar. Pero, por ejemplo:

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

Entonces C contará el número de tick s que se produjeron en el cálculo.

De hecho, se puede reemplazar Int con cualquier tipo y con cualquier (+)asociativo operador y obtener una mónada. Esto es lo que es una mónada Writer en general. Si el operador no es asociativo, entonces fallará la tercera ley (¿puedes ver por qué?).