Alla ricerca di critiche costruttive sull'implementazione di monad

Question

Sto imparando le monadi, questa è la mia prima opera (a parte la banale monade). Sentiti libero di criticare tutto in esso spietatamente. Sono particolarmente interessato al tipo di risposte "più idiomatiche" e "più eleganti".

Questa monade conta il numero di associazioni eseguite.

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

Stilisticamente questo è molto bello. Nel mondo reale, mi aspetterei un 60% di probabilità di questa notazione al posto di quello che hai dato:

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

ma che è così piccola non vale la pena menzionare.

Su una nota più seria, non stilistica ma semantica: questa non è una monade. In realtà, viola tutte e tre le leggi della monade.

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

(Dove (>=>) è definito come f >=> g = \x -> f x >>= g. Se (>>=) è considerato un operatore "applicazione", quindi (>=>) è l'operatore di composizione corrispondente. Mi piace affermare la terza legge utilizzando questo operatore perché porta la terza legge di che significa: associatività)

Con questi calcoli:.

(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 

Questo non è solo un errore nella realizzazione - non c'è monade che "conta il numero di lega". È deve violare le leggi (1) e (2). Il fatto che il tuo violi la legge (3) è comunque un errore di implementazione.

Il problema è che f nella definizione di (>>=) potrebbe restituire un'azione che ha più di un binding e che si sta ignorando. È necessario aggiungere il numero di lega dagli argomenti destro e sinistro:

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

Ciò correttamente contare il numero di lega, e in grado di soddisfare la terza legge, che è la legge associatività. Non soddisferà gli altri due. Tuttavia, se si lascia cadere la +1 da questa definizione, allora si fai ottenere una vera e propria monade, che è equivalente al Writer Monade sul + monoide. Questo fondamentalmente somma insieme i risultati di tutte le subcomputazioni. Potresti usare questo per contare il numero di dei numeri, non solo per legare - il binding è troppo speciale per contare. Ma, per esempio:

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

Poi C conta il numero di tick s che si sono verificati nel calcolo.

In realtà, è possibile sostituire Int con qualsiasi tipo e con qualsiasi (+)associativa operatore e ottenere una monade. Questo è ciò che una monade Writer è in generale. Se l'operatore non è associativo, fallirà la terza legge (capisci perché?).