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

Question

我正在学习函数式编程，并且有一些关于 monad 的问题(也许很明显，但不适合我:))。每个单子(monad)都是一个应用仿函数。应用仿函数又可以定义为更高种类的类型，如下( 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

它遵循可遍历仿函数定律。

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

让我们从你的开始

reverseApList(lst).foldMap(nt)

也可以写成

lst.sequence.foldMap(nt)

现在我们要应用 naturality law of Traversable functors ，以 _.foldMap(nt) 作为自然变换 nat。为了使其适用，我们的自然变换必须是一个应用同态，用 the two extra conditions 表示。 。但我们已经知道，我们的自然变换是单子(monad)同态，它比应用同态更强(保留更多结构)。因此，我们可以继续适用该法律并获得

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

现在仅使用链接的 scalaz 文件中的定律就可以证明(尽管以迂回的方式)，最后一个 sequence 到 Id 实际上是一个空操作。我们得到

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

这就是我们想要展示的内容。

<小时/>

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

• 对于任何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)))