带有 flatMap 的集合是 monad 吗？

Question

Scala 具有定义

的特征 Iterable[A]

def flatMap[B](f: (A) ⇒ GenTraversableOnce[B]): Iterable[B]

这肯定看起来 像 monad 上的 bind 函数，文档暗示它是 monad，但有两个反对意见，一个次要的和一个主要的：

次要的：传入函数的返回类型是this GenTraversableOnce。我认为这只是判断monad-ness时可以忽略的便利。
主要的：monad 的 "value" 是它包含的所有值的列表，但是函数一次被赋予一个值。

这些问题是否破坏了集合的单子性？

Answer 1

要在不包括 Scalaz 和类别理论的核心 Scala 上下文中回答您的问题，而核心 Scala 没有特征 class 或名为 "Monad" 的对象，它确实实现了一个对象-面向 monad 的概念，我将其称为 Orderskian monad，因为它主要是由 Martin Ordersky（根据 http://igstan.ro/posts/2012-08-23-scala-s-flatmap-is-not-haskell-s.html 和 Adrian Moors）发明和实现的。

一个 Orderskian monad 至少需要 map、flatmap 和 withFilter 函数，如 Martin Odersky 在 "Programming In Scala" (2Ed:PDF edition:chapter 23:page 531) 中所解释的，他指出 "Therefore, map, flatMap and withFilter can be seen as an object-oriented version of the functional concept of monad." 基于此，Scala Collections 是 Orderskian monad。

要回答包括 Scalaz 在内的问题，它需要 scalaz.Monad 实现来扩展 Monad 特性并实现两个抽象函数 pure 和 bind，以满足要求它们的三个定律 (http://scalaz.github.io/scalaz/scalaz-2.9.1-6.0.2/doc/index.html#scalaz.Monad ).核心 Scala 集合不满足这些要求，因此没有什么可以破坏它们的 scalaz.Monad-ness，因为它从未存在过。就 scalaz.Monad 模拟范畴论单子而言，该论点适用于后者。

Answer 2

我认为带有 flatMap 的集合不一定是 monad。它不一定适合 monad laws. These laws are probably better explained in Functional Programming in Scala 我做不到。

最近我从一位同事那里听到了一个关于什么是 Scala 中的 monad 的简单而实用的解释（带有自我意识）：something you can put in a for comprehension。

我不是 monad 专家，但在我看来这不是真的，对于带有 flatMap 的集合也是如此。最明显的例子是在 Scala lib Either 中，因为它不是右偏的，并且它没有任何 flatMap 方法，直到你将它投影到一边（并且这个投影不是单子的，因为它 returns任何一个）。据我了解，类型不是 monad（或 monoid 或其他），但类型可能有 monad（或什至很多？不确定，但任何示例都会感兴趣（但也许 Either 是好的一个？)).

我认为 Scala 是一种实用的语言，有时忘记严格的规则并帮助程序员更轻松地完成工作是很有用的。并非所有程序员都关心什么是 monad，但许多人可能希望在某些时候将 List[Set[Int]] 展平，而 flatMap 可能会帮助他们。

这让我想起了这个博客 post 其中 Future type is considered as copointed for tests。

Answer 3

"major" 的问题更容易回答：不，不是，因为那不是它的意思。一个 monad 不需要有任何特定的 "value" 或 none，只需要以特定的方式与函数组合。

对于 "minor"，您对类型的关注是正确的。正确地说，monad 是一个幺半群（有一些额外的约束），这意味着它是一个具有特定操作的集合。据我所知，这个集合的元素是 A => M[B] 类型的东西（在 scalaz 中，这种类型称为 Kleisli）； flatMap是幺半群的|+|操作。

Scala 中 all possible A => Iterable[B] 的集合是否形成关于此操作的幺半群（以及合适的身份选择）？不，非常不，因为有很多可能 A => Iterable[B] 违反了 monad 法则。对于一个简单的例子，{a: A => throw new RuntimeException()}。一个更严重的例子是，例如。如果 Set 出现在 flatMap 链中，这会破坏关联性：假设我们有：

f: String => Iterable[String] = {s => List(s)}
g: String => Iterable[String] = {s => Set(s)}
h: String => Iterable[String] = {s => List("hi", "hi")}

然后

((f |+| g) |+| h).apply("hi") = List("hi") flatMap h = List("hi", "hi")

但是

(f |+| (g |+| h)).apply("hi") = List("hi") flatMap {s => Set("hi")} = List("hi")

这令人沮丧，因为幺半群的全部意义在于我们可以编写 f |+| g |+| h 而不必担心我们以何种方式评估它。回到 monad，关键是我们应该能够写

for {
  a <- f("hi")
  b <- g(a)
  c <- h(b)
} yield c

不用担心 flatMap 的组成顺序。但是对于上面的 f、g 和 h，您期望哪个答案上面的代码给？（我知道答案，但这很令人惊讶）。对于真正的 monad，除了作为 scala 编译器实现细节之外，这个问题不会出现，因为无论哪种方式，答案都是相同的。

另一方面，的特定子集是否可能 A => M[B]，例如"the set of all A => List[B] implemented under the scalazzi safe subset of scala"，根据 flatMap 的定义形成一个 monad？是的（至少对于两个 Scala 函数何时相等的普遍接受的定义而言）。这适用于几个子集。但我认为说 scala Iterables in general 在 flatMap.

下形成 monad 并不完全正确

Answer 4

您的标题问题的答案是可能。具有 flatMap 的 collection 不足以成为 monad，但如果它满足一些进一步的条件，它可能是 monad。

您的“小”问题肯定会破坏 Iterable 的单子性（“monad-ness”的正确词）。这是因为 Iterable 和 GenTraversableOnce 的许多子类型 不是单子 。因此，Iterable 不是 monad。

你的“主要”问题根本不是问题。例如，List monad 的 flatMap 的函数参数一次接收一个 List 的元素。列表中的每个元素都会生成一个完整的结果列表，这些列表最后都连接在一起。

幸运的是，判断一个东西是否是 monad 真的很容易！我们只需要知道 monad.

的精确定义

成为 monad 的要求

一个 monad 必须是一个接受一个类型参数的类型构造函数 F[_]。例如，F 可以是 List、Function0、Option 等
一个单子单元。这是一个函数，它接受任何类型 A 的值并生成 F[A].
单子组合操作。它是一个接受类型 A => F[B] 的函数和类型 B => F[C] 的函数并生成类型 A => F[C].

（还有其他的表述方式，但我觉得这个表述很容易解释）

为 Iterable 考虑这些。它肯定需要一种类型的参数。它在函数 Iterable(_) 中有一个排序单元。虽然它的 flatMap 操作并不严格符合，但我们当然可以写成：

def unit[A](a: A): Iterable[A] = Iterable(a)

def compose[A,B,C](f: A => Iterable[B],
                   g: B => Iterable[C]): A => Iterable[C] =
  a => f(a).flatMap(g)

但这并不能使它成为单子，因为单子还必须满足某些法则:

关联性：compose(compose(f, g), h) = compose(f, compose(g, h))
身份：compose(unit, f) = f = compose(f, unit)

打破这些定律的一个简单方法，as lmm has already pointed out，是将 Set 和 List 混合为这些表达式中的 Iterable。

“半单曲”

虽然只有 flatMap（而不是 unit）的类型构造不是单子，但它可能形成所谓的 Kleisli semigroupoid。要求与 monad 相同，只是没有 unit 操作和恒等律。

（关于术语的注释：一个 monad 形成一个 Kleisli 范畴，而一个 semigroupoid 是一个没有恒等式的范畴。）

For-comprehensions

Scala 的 for-comprehensions 在技术上比 semigroupoids 甚至更少要求（只是 map 和 flatMap 操作服从 no法律）。但是将它们与至少不是半群群的事物一起使用会产生非常奇怪和令人惊讶的效果。例如，这意味着您不能在 for-comprehension 中内联定义。如果你有

val p = for {
  x <- foo
  y <- bar
} yield x + y

而foo的定义是

val foo = for {
  a <- baz
  b <- qux
} yield a * b

除非结合律成立，否则我们不能依赖于能够将其重写为：

val p = for {
  a <- baz
  b <- qux
  y <- bar
} yield a * b + y

不能进行这种替换是非常违反直觉的。所以大多数时候，当我们使用 for-comprehensions 时，我们假设我们在一个 monad 中工作（即使我们没有意识到这一点），或者至少是一个 Kleisli semigroupoid。

但请注意，这种替换通常不适用于 Iterable:

scala> val bar: Iterable[Int] = List(1,2,3)
bar: Iterable[Int] = List(1, 2, 3)

scala> val baz: Iterable[Int] = Set(1,2,3)
baz: Iterable[Int] = Set(1, 2, 3)

scala> val qux: Iterable[Int] = List(1,1)
qux: Iterable[Int] = List(1, 1)

scala> val foo = for {
     |   x <- bar
     |   y <- baz
     | } yield x * y
foo: Iterable[Int] = List(1, 2, 3, 2, 4, 6, 3, 6, 9)

scala> for {
     |   x <- foo
     |   y <- qux
     | } yield x + y
res0: Iterable[Int] = List(2, 2, 3, 3, 4, 4, 3, 3, 5, 5, 7, 7, 4, 4, 7, 7, 10, 10)

scala> for {
     |   x <- bar
     |   y <- baz
     |   z <- qux
     | } yield x * y + z
res1: Iterable[Int] = List(2, 3, 4, 3, 5, 7, 4, 7, 10)

有关 monad 的更多信息

有关 Scala 中 monad 的更多信息，包括的含义以及我们为什么要关心，我鼓励您查看 chapter 11 of my book.

Answer 5

Scala 集合方法 flatMap 和 flatten 比 monadic 更强大 flatMap/flatten。看这里：https://www.slideshare.net/pjschwarz/scala-collection-methods-flatmap-and-flatten-are-more-powerful-than-monadic-flatmap-and-flatten

带有 flatMap 的集合是 monad 吗？

Is a collection with flatMap a monad?

monads

scala

成为 monad 的要求

“半单曲”

For-comprehensions

有关 monad 的更多信息