解释免费单子列表与解释列表中的免费单子列表(Interpreting a list of free monads vs. interpreting a free monad of a list)

解释免费单子列表与解释列表中的免费单子列表(Interpreting a list of free monads vs. interpreting a free monad of a list)

我正在学习函数式编程，并且有一些（也许很明显，但不适合我:)）关于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)相同？ 它是遵循适用函数法还是有其他原因？ 你能解释一下吗？

I'm learning functional programming and have some (maybe obvious, but not for me :) ) question about monad. Every monad is an applicative functor. Applicative functor in turn can be defined as a higher-kinded type as follows (pure method omitted):

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

As far as I understand this typeclass means that we can take two values of F[A], F[B] and a function (A, B) => C and construct F[C].

This property enables us to construct the list reversing function:

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

Let we have

trait SomeType[A]

Now consider

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

QUESTION: Why are lst.map(_.foldMap(nt)) and reverseApList(lst).foldMap(nt) the same? Is it following from applicative functor laws or there is another reason? Can you please explain?

最满意答案

它遵循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文件中的规则，它是可证明的（尽管以迂回的方式），通过Id最后一个sequence实际上是无操作的。 我们得到

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

这是我们想要展示的。

---

¹ ：一个自然变换h: M ~> N M〜 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)))

It follows from the laws of Traversable functors.

First, realize that _.foldMap(nt) is itself a natural transformation from MyFree to Id. Moreover, by the very definition of what it means to be a free monad, it is required to be a monad homomorphism¹ (for any nt).

Let's start from your

reverseApList(lst).foldMap(nt)

which can also be written as

lst.sequence.foldMap(nt)

Now we are going to apply the 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. But we already know that our natural transformation is a monad homomorphism, which is even stronger (preserves more structure) than an applicative homomorphism. We may therefore proceed to apply this law and obtain

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

Now using just the laws in the linked scalaz file it is provable (although in a roundabout way) that this last sequence through Id is actually a no-op. We get

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

which is what we wanted to show.

---

¹ : A natural transformation h: M ~> N is a monad homomorphism if it preserves the monadic structure, i.e. if it satisfies

for any a: A: h(Monad[M].point[A](a)) = Monad[N].point[A](a) for any ma: M[A] and f: A => M[B]: h(ma.flatMap(f)) = h(ma).flatMap(a => h(f(a)))