解释自由 monad 列表与解释列表的自由 monad

Question

我正在学习函数式编程并且有一些（可能很明显，但对我来说不是:)）关于 monad 的问题。每个 monad 都是一个应用函子。 Applicative functor 又可以定义为更高种类的类型，如下所示（pure 方法省略）：

trait ApplicativeFunctor[F[_]]{
   def ap[A](fa: F[A])(f: F[A => B]): F[B]
}

据我了解，这个类型类意味着我们可以取 F[A]、F[B] 的两个值和一个函数 (A, B) => C 并构造 F[C]。

这个属性使我们能够构造列表反转函数：

def reverseApList[F[_]: ApplicativeFunctor, A](lst: List[F[A]]): F[List[A]]

让我们有

trait SomeType[A]

现在考虑

type MyFree[A] = Free[SomeType, A] 
val nt: NaturalTransformation[SomeType, Id]
val lst: List[MyFree[Int]]

问题： 为什么 lst.map(_.foldMap(nt)) 和 reverseApList(lst).foldMap(nt) 相同？它是遵循适用函子定律还是有其他原因？能解释一下吗？

Answer 1

它遵循 Traversable 函子的定律。

首先，要认识到 _.foldMap(nt) 本身就是从 MyFree 到 Id 的自然转换。此外，根据自由单子的定义，它必须是 单子同态¹（对于任何 nt).

让我们从您的

开始

reverseApList(lst).foldMap(nt)

也可以写成

lst.sequence.foldMap(nt)

现在我们要应用 naturality law of Traversable functors, with _.foldMap(nt) as the natural transformation nat. For it to be applicable, our natural transformation has to be an applicative homomorphism, which is expressed by the two extra conditions。但是我们已经知道我们的自然变换是单子同态，它比应用同态更强（保留更多结构）。因此，我们可能会继续应用此法律并获得

lst.map(_.foldMap(nt)).sequence : Id[List[Int]]

现在仅使用链接的 scalaz 文件中的定律就可以证明（尽管以迂回的方式）最后 sequence 到 Id 实际上是 no-op。我们得到

lst.map(_.foldMap(nt))          : List[Id[Int]]

这就是我们想要展示的。

¹ ：自然变换 h: M ~> N 是单子同态，如果它保留单子结构，即如果它满足

对于任何 a: A:
h(Monad[M].point[A](a)) = Monad[N].point[A](a)
对于任何 ma: M[A] 和 f: A => M[B]:
h(ma.flatMap(f)) = h(ma).flatMap(a => h(f(a)))

解释自由 monad 列表与解释列表的自由 monad

Interpreting a list of free monads vs. interpreting a free monad of a list

monads

scala

scalaz