free monad 应该基于的仿函数在哪里
Where is that functor which free monad is supposed to be based on
我试图理解自由 monad 的概念，但我对 cats's docs 的第一句话感到困惑
A free monad is a construction which allows you to build a monad from
any Functor
我的困惑主要与KVStoreA的"freeing"ADT过程中没有任何函子used\created有关。 ADT 或类似的东西没有仿函数的实现。但是，Free[S[_],A] 的文档说 S must me a functor:
A free operational monad for some functor S.
免费 monad 应该基于的仿函数在哪里？
事实是，Free monad 可以通过几种不同的方式使用。为了使用其中之一，您假设您有一些仿函数 S[_]，它将定义一些 Functor[S]，您将通过允许某种排序将 S[*] 提升为 Free[S, *]对原始 S:
的扩展
Free[S, A] = S[A] or A
This is not valid Scala! They way it is actually implemented is using ADT. This only serves as an explanation of the idea.
这样，如果您有 S[A] 并且您 map 它与 f: A => B，您将使用 Functor[S] 并收到 S[B]。但是如果你 flatMap 它与 f: A => Free[S, B]...你仍然可以使用 Functor[S] 计算并接收 S[Free[S, B]]。这就是这段代码的内容。记住 Free[S, A] = S[A] or A 你可以看到这会变成 S[S[S[...]]] 并且如果不是 Free[S, A] 的 or A 部分它可以无限嵌套，这会让我们在某个时候停下来。
当然我们不会一次全部计算，Free 通常使用 trampoline 一次只计算一个东西，所以我们不会一次嵌套很多。
sealed abstract class Free[S[_], A] extends Product with Serializable {
// ...
}
object Free extends FreeInstances {
/**
* Return from the computation with the given value.
*/
final private[free] case class Pure[S[_], A](a: A) extends Free[S, A]
/** Suspend the computation with the given suspension. */
final private[free] case class Suspend[S[_], A](a: S[A]) extends Free[S, A]
/** Call a subroutine and continue with the given function. */
final private[free] case class FlatMapped[S[_], B, C](c: Free[S, C], f: C => Free[S, B]) extends Free[S, B]
...
}
This trampoline representation implements the same idea as S[A] or A but it allows running computations one step at a time. It also shows that Free[S, *] is S[*] algebra extended by pure and flatMap operations (that assume nothing about S), which justifies calling Free a free algebra.
实际上，在我们决定 运行 计算之前，我们只有延迟评估的数据结构。 运行ning 的一种方法是调用 free.run 你 have defined for Free in cats - 它将使用蹦床评估每个嵌套，一次一个，但随后它将使用 Comonad[S] 来提取值——因此我们将在进行时摆脱嵌套。 Comonad[S] 也是 Functor[S]，这就是为什么我们不必单独提供它来完成所有这些 map。
但这是 运行宁事的一种方式。 运行 的另一种方式是假设我们正在使用 Free 记录 map、flatMap 和 pure 操作。为此，我们根本不需要 Functor[S]。我们可能会决定 run 使用 Comonad[S] 的东西，但我们也可能会决定其他东西。如果我们将 S[_] 翻译成一些 M[_]，但我们知道这个 M[_] 有一个 Monad[M] 怎么办？在这种情况下，我们根本不必使用 Functor[S]！我们会运行翻译S ~> M，然后在上面贴上map或者flatMap，里面的S也会用同样的S ~> M机制翻译。这就是 foldMap does - 它要求我们提供一个自然转换 S ~> M 而 Monad[M] 和 Functor[S] 的实例是完全没有必要的。虽然在概念上我们仍然可以将 S 视为一个函子，但我们不需要依赖任何函子属性，而不是 Functor[S].
的形式
所以最后回答你的问题 - 当我们还处于 "recording operations" 阶段时使用 Free 我们不必假设 S 是一个函子，所以我们不需要Functor[S]。当我们想将 Free[S, A] 解释成某些东西时——这可能是实际需要仿函数的地方，例如如果我们想把运行Free[S, A]变成A。但是对于某些解释，例如foldMap（恕我直言，这是最受欢迎的之一）这不是必需的，因为我们将 S 视为普通数据。
我试图理解自由 monad 的概念，但我对 cats's docs 的第一句话感到困惑
A free monad is a construction which allows you to build a monad from any Functor
我的困惑主要与KVStoreA的"freeing"ADT过程中没有任何函子used\created有关。 ADT 或类似的东西没有仿函数的实现。但是，Free[S[_],A] 的文档说 S must me a functor:
A free operational monad for some functor
S.
免费 monad 应该基于的仿函数在哪里？
事实是，Free monad 可以通过几种不同的方式使用。为了使用其中之一，您假设您有一些仿函数 S[_]，它将定义一些 Functor[S]，您将通过允许某种排序将 S[*] 提升为 Free[S, *]对原始 S:
Free[S, A] = S[A] or A
This is not valid Scala! They way it is actually implemented is using ADT. This only serves as an explanation of the idea.
这样，如果您有 S[A] 并且您 map 它与 f: A => B，您将使用 Functor[S] 并收到 S[B]。但是如果你 flatMap 它与 f: A => Free[S, B]...你仍然可以使用 Functor[S] 计算并接收 S[Free[S, B]]。这就是这段代码的内容。记住 Free[S, A] = S[A] or A 你可以看到这会变成 S[S[S[...]]] 并且如果不是 Free[S, A] 的 or A 部分它可以无限嵌套，这会让我们在某个时候停下来。
当然我们不会一次全部计算，Free 通常使用 trampoline 一次只计算一个东西，所以我们不会一次嵌套很多。
sealed abstract class Free[S[_], A] extends Product with Serializable {
// ...
}
object Free extends FreeInstances {
/**
* Return from the computation with the given value.
*/
final private[free] case class Pure[S[_], A](a: A) extends Free[S, A]
/** Suspend the computation with the given suspension. */
final private[free] case class Suspend[S[_], A](a: S[A]) extends Free[S, A]
/** Call a subroutine and continue with the given function. */
final private[free] case class FlatMapped[S[_], B, C](c: Free[S, C], f: C => Free[S, B]) extends Free[S, B]
...
}
This trampoline representation implements the same idea as
S[A] or Abut it allows running computations one step at a time. It also shows thatFree[S, *]isS[*]algebra extended bypureandflatMapoperations (that assume nothing about S), which justifies calling Free a free algebra.
实际上，在我们决定 运行 计算之前，我们只有延迟评估的数据结构。 运行ning 的一种方法是调用 free.run 你 have defined for Free in cats - 它将使用蹦床评估每个嵌套，一次一个，但随后它将使用 Comonad[S] 来提取值——因此我们将在进行时摆脱嵌套。 Comonad[S] 也是 Functor[S]，这就是为什么我们不必单独提供它来完成所有这些 map。
但这是 运行宁事的一种方式。 运行 的另一种方式是假设我们正在使用 Free 记录 map、flatMap 和 pure 操作。为此，我们根本不需要 Functor[S]。我们可能会决定 run 使用 Comonad[S] 的东西，但我们也可能会决定其他东西。如果我们将 S[_] 翻译成一些 M[_]，但我们知道这个 M[_] 有一个 Monad[M] 怎么办？在这种情况下，我们根本不必使用 Functor[S]！我们会运行翻译S ~> M，然后在上面贴上map或者flatMap，里面的S也会用同样的S ~> M机制翻译。这就是 foldMap does - 它要求我们提供一个自然转换 S ~> M 而 Monad[M] 和 Functor[S] 的实例是完全没有必要的。虽然在概念上我们仍然可以将 S 视为一个函子，但我们不需要依赖任何函子属性，而不是 Functor[S].
所以最后回答你的问题 - 当我们还处于 "recording operations" 阶段时使用 Free 我们不必假设 S 是一个函子，所以我们不需要Functor[S]。当我们想将 Free[S, A] 解释成某些东西时——这可能是实际需要仿函数的地方，例如如果我们想把运行Free[S, A]变成A。但是对于某些解释，例如foldMap（恕我直言，这是最受欢迎的之一）这不是必需的，因为我们将 S 视为普通数据。