В поисках конструктивной критики по реализации монады

Question

Я изучаю монады, это моя первая рабочая (кроме тривиальной монады). Не стесняйтесь критиковать все в нем безжалостно. Меня особенно интересуют «более идиоматические» и «более элегантные» ответы.

Эта монада подсчитывает количество выполненных привязок.

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

Стилистически это очень приятно.В реальном мире я бы ожидал 60-процентную вероятность этой записи вместо той, которую вы дали:

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

Но это настолько незначительно, что вряд ли стоит упоминать.

более серьезное замечание, не стилистическое, а семантическое: это не монада.Фактически он нарушает все три закона монады.

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

(где (>=>) определяется как f >=> g = \x -> f x >>= g. Если (>>=) считается оператором "приложения", то (>=>) являетсясоответствующий оператор композиции. Мне нравится формулировать третий закон, используя этот оператор, потому что он выявляет значение третьего закона: ассоциативность.)

С этими вычислениями:

(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

Это не просто ошибка в вашей реализации - нет монады, которая "считается"количество привязок ".Оно должно нарушать законы (1) и (2).Однако тот факт, что ваш нарушает закон (3), является ошибкой реализации.

Проблема в том, что f в определении (>>=) может вернуть действие, имеющее более одной привязки, и выигнорируя это.Вам нужно добавить количество привязок из левого и правого аргументов:

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

Это будет правильно подсчитывать количество привязок и будет удовлетворять третьему закону, который является ассоциативностьюзакон.Это не удовлетворит двух других.Однако, если вы отбросите +1 из этого определения, то вы do получите настоящую монаду, что эквивалентно монаде Writer над моноидом +.Это в основном складывает воедино результаты всех вычислений.Вы можете использовать это для подсчета числа что-то , только не связывает - привязка слишком особенная для подсчета.Но, например:

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

Тогда C будет подсчитывать количество tick s, которые произошли в вычислении.

Фактически, вы можете заменить Int на любойнаберите (+) с любым ассоциативным оператором и получите монаду.Вот что такое Writer монада в целом.Если оператор не является ассоциативным, то это нарушит третий закон (понимаете почему?).