Ищу конструктивную критику реализации монады

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

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

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

Ответ 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 из этого определения, вы получаете реальную монаду, которая эквивалентна монаде Writer над моноидом +. Это в основном объединяет результаты всех подвычислений. Вы можете использовать это, чтобы подсчитать количество вещей, просто не связывать - bind слишком особенный, чтобы считать. Но, например:

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

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

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