Szukanie konstruktywnej krytyki przy realizacji monad

Question

Szukanie konstruktywnej krytyki przy realizacji monad

Uczę się monad, to moja pierwsza robocza (poza trywialną monadą). Możesz bezlitośnie krytykować wszystko w nim. Szczególnie interesują mnie odpowiedzi" bardziej idiomatyczne "i" bardziej eleganckie".

Monada ta liczy liczbę wykonanych wiązań.

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

30

haskell monads idiomatic

Author: luqui, 2011-01-22

Source

1 answers

score 89 · Accepted Answer

Stylistycznie to jest bardzo ładne. W realnym świecie spodziewałbym się 60% szansy na taką notację zamiast tej, którą dałeś: {]}

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

Ale To jest tak niewielkie, że nie warto o tym wspominać.

Mówiąc poważniej, nie stylistycznie, ale semantycznie: to nie jest monada. W rzeczywistości, to narusza wszystkie trzy prawa monad.

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

(gdzie (>=>) jest zdefiniowane jako f >=> g = \x -> f x >>= g. Jeśli (>>=) jest operatorem "aplikacji", to {[7] } jest odpowiednim składem centrala. Lubię określać trzecie prawo używając tego operatora, ponieważ wydobywa ono znaczenie trzeciego prawa: Asocjacja.)

Z tymi obliczeniami:

(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

To nie jest tylko błąd w Twojej implementacji - nie ma monady, która "zlicza liczbę bindów". To musi naruszać prawa (1) i (2). Fakt, że Twoje narusza prawo (3) jest jednak błędem implementacji.

The trouble czy f w definicji (>>=) może zwrócić akcję, która ma więcej niż jedno bind, a Ty to ignorujesz. Musisz dodać liczbę bindów z lewego i prawego argumentu:

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

To poprawnie policzy liczbę wiązań i spełni trzecie prawo, którym jest prawo asocjacji. To nie zadowoli pozostałych dwóch. Jeśli jednak odrzucisz +1 z tej definicji, to uzyskasz rzeczywistą monadę, która jest równoważna Writer monada nad + monoidem. To w zasadzie sumuje wyniki wszystkich subkomputacji. Możesz użyć tego do policzenia liczby somethings, po prostu nie wiąże -- bind jest zbyt specjalny, aby zliczyć. Ale, na przykład:

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

Następnie C policzy liczbę tickS, które wystąpiły w obliczeniach.

W rzeczywistości, można zastąpić Int dowolnym typem i (+) dowolnym operatorem asocjacyjnym i uzyskać monadę. Tym właśnie jest Writer monada ogólnie. Jeśli operator nie jest asocjacyjny, to zawiedzie trzecie prawo (czy widzisz dlaczego?).