在monad实现上寻求建设性的批评 [英] Seeking constructive criticism on monad implementation

问题描述

我正在学习单子，这是我第一个工作的人（除了微不足道的单子）。随意批评其中的一切无情。我对更习惯和更优雅的回应特别感兴趣。

这个monad计算执行绑定的次数。

  data C a = C {value :: a，count :: Int}派生（显示）
 
实例Monad C其中
（>> =）（C xc）f = C（值$ fx）（c + 1）
 return x = C x 0 
 
 add ::（Num a）=> a  - > a  - > C a 
 add x y =返回$ x + y 
 
  - 更简单的方法来做到这一点？ foldM显然是不同的。 
 mysum [x] = return x 
 mysum（x：xs）= mysum xs>> = add x 
  

解决方案

文体上这是非常好的。在现实世界中，我希望这个符号的概率是60％，而不是你给的那个：

  C xc> > = f = C（价值$ fx）（c + 1）
  

这是不值得一提的。

更严肃的说，不是文体而是语义：这不是单子。事实上，它违反了所有三项单子法。

 （1）return x>> = f = fx $ （3）m> =（f> => g）=（m>> = f）>>>>>>>>> ; = g 
  

（其中（> =>）定义为 f> => g = \ x - > fx>> = g 如果（ > =）被认为是应用程序运算符，则（> =>）是相应的组合运算符。使用这个算子来陈述第三个定律，因为它带出了第三定律的意义：相关性。）

使用这些计算：
$ b $ （1）：

  return 0>> = return 
 = C 0 0> > =返回
 = C（值$返回0）1 
 = C 0 1 
不等于返回0 = C 0 0 
  

<2>：

  C 0 0> > =返回
 = C（值$返回0）1 
 = C 0 1 
不等于C 0 0 
  

（3）

  C 0 0>> =（return> =>返回）
 = C（值$（返回> =>返回）0 $ 1 
 = C（值$返回0>> =返回）1 
 = C $ C 0 1）1 
 = C 0 1 
 
不等于：
 
（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 in （>> =）的定义可能会返回一个包含多个绑定的操作，而您忽略了该操作。您需要从左侧和右侧参数中添加绑定的数量：

  C xc> > = f = C y（c + c'+ 1）
其中
 C y c'= fx 
  

这将正确计算绑定次数，并将满足第三个定律，即结合律。它不会满足其他两个。然而，如果你从这个定义中删除 +1 ，那么你得到一个真正的monad，这相当于 Writer monad覆盖 + monoid。这基本上将所有子计算的结果加在一起。你可以使用它来计算 的数量，只是不绑定 - 绑定是非常特殊的数量。但是，例如：

  tick :: C（）
 tick = C（）1 
  

然后 C 会计算 tick 发生在计算中。

实际上，您可以替换 Int 与任何类型和（+）与任何关联运算符并获得一个monad。这是一般的 Writer monad。如果操作员不是联想的，那么这会违反第三条法则（你能看出为什么？）。

I'm learning monads, this is my first working one (aside from the trivial monad). Feel free to criticize everything in it ruthlessly. I'm especially interested in "more idiomatic" and "more elegant" kind of responses.

This monad counts the number of binds performed.

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

解决方案

Stylistically this is very nice. In the real world, I would expect a 60% chance of this notation instead of the one you gave:

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

But that is so minor it is hardly worth mentioning.

On a more serious note, not stylistic but semantic: this is not a monad. In fact, it violates all three of the monad laws.

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

(Where (>=>) is defined as f >=> g = \x -> f x >>= g. If (>>=) is considered an "application" operator, then (>=>) is the corresponding composition operator. I like to state the third law using this operator because it brings out the third law's meaning: associativity.)

With these computations:

(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

This isn't just an error in your implementation -- there is no monad that "counts the number of binds". It must violate laws (1) and (2). The fact that yours violates law (3) is an implementation error, however.

The trouble is that f in the definition of (>>=) might return an action that has more than one bind, and you are ignoring that. You need to add the number of binds from the left and right arguments:

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

This will correctly count the number of binds, and will satisfy the third law, which is the associativity law. It won't satisfy the other two. However, if you drop the +1 from this definition, then you do get a real monad, which is equivalent to the Writer monad over the + monoid. This basically adds together the results of all subcomputations. You could use this to count the number of somethings, just not binds -- bind is too special to count. But, for example:

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

Then C will count the number of ticks that occurred in the computation.

In fact, you can replace Int with any type and (+) with any associative operator and get a monad. This is what a Writer monad is in general. If the operator is not associative, then this will fail the third law (can you see why?).

这篇关于在monad实现上寻求建设性的批评的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！