解释免费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

它遵循Traversable仿函数的定律.

首先,要认识到_.foldMap(nt)是自己从一个自然转化MyFree来Id.而且,通过对自由monad的意义的定义,它必须是monad同态¹(对于任何nt).

让我们从你的开始

reverseApList(lst).foldMap(nt)

也可以写成

lst.sequence.foldMap(nt)

现在,我们要运用Traversable的函子的自然性的法律,与_.foldMap(nt)作为自然转化nat.为了适用它,我们的自然变换必须是一个适用的同态,它由两个额外条件表示.但我们已经知道,我们的自然变换是一个单子同态,它比应用同态更强(保留更多的结构).因此,我们可以继续适用这项法律并获得

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

现在只使用链接的scalaz文件中的规则,可证明(尽管以迂回的方式),最后sequence通过Id实际上是无操作.我们得到了

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

这是我们想要展示的.

¹:自然变换h: M ~> N是monad同态,如果它保留了monadic结构,即它是否满足

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