FunctionK 类型参数的界限

Question

我正在使用 cats FreeMonad。这是代数的简化版本：

sealed trait Op[A]

object Op {
    final case class Get[T](name: String) extends Op[T]

    type OpF[A] = Free[Op, A]

    def get[T](name: String): OpF[T] = liftF[Op, T](Get[T](name))
}

其中一个解释器将是第三方库的包装器，在此处称为 Client，其 get 方法的签名类似于：

class Client {
    def get[O <: Resource](name: String)
        (implicit f: Format[O], d: Definition[O]): Future[O] = ???
}

我的问题是如何在我的实施中对该要求进行编码？

class FutureOp extends (Op ~> Future) {
    val client = new Client()

    def apply[A](fa: Op[A]): Future[A] =
        fa match {
            case Get(name: String) =>
                client.get[A](name)
        }
}

我尝试了一些方法，比如为我的 apply（比如 apply[A <: Resource : Format : Definition]）引入界限，但没有用。

我知道FunctionK是转换一阶类型的值，但是有没有我可以在其中编码类型参数的要求？

我打算像这样使用它：

def run[F[_]: Monad, A](intp: Op ~> F, op: OpF[A]): F[A] = op.foldMap(intp)

val p: Op.OpF[Foo] = Op.get[Foo]("foo")

val i = new FutureOp()

run(i, d)

Answer 1

(我原来的回答也有同样的想法，但显然没有提供足够的实现细节。这次，我写了一个更详细的 step-by-step 指南，对每个中间步骤进行了讨论. 每个部分都包含一个单独的可编译代码片段。)

TL;DR

在 get[T] 中出现的每个类型 T 都需要隐式，因此必须在 DSL-program 被 构造时插入和存储它们 ，而不是在 执行时 。这解决了隐式问题。
有一个通用策略可以使用模式匹配从几个 受限的自然变换 trait RNT[R, F[_ <: R], G[_]]{ def apply[A <: R](x: F[A]): G[A] } 中粘合一个自然变换 ~>。这解决了 A <: Resource 类型绑定的问题。详情如下。

在你的问题中，你有两个不同的问题：

隐式 Format 和 Definition
<: Resource-类型绑定

我想分别对待这两个问题，并为这两个问题提供可重用的解决策略。然后我会将这两种策略应用于您的问题。

我下面的回答结构如下：

首先，我会根据我的理解总结一下你的问题。
然后我将解释如何处理隐式，忽略类型绑定。
然后我将处理类型绑定，这次忽略隐式。
最后，我将这两种策略都应用于您的特定问题。

从今以后，我假设你有scalaVersion2.12.4，依赖项

libraryDependencies += "org.typelevel" %% "cats-core" % "1.0.1"
libraryDependencies += "org.typelevel" %% "cats-free" % "1.0.1"

然后你插入

import scala.language.higherKinds

在适当的地方。请注意，解决方案策略并不特定于此特定的 Scala 版本或 cats 库。

设置

本节的目标是确保我解决了正确的问题，并提供非常简单的 mock-up 定义 Resource、Format、Client 等，所以这个答案是 self-contained 并且可编译。

我假设您想使用 Free monad 构建一个小的领域特定语言。理想情况下，您希望拥有一个看起来大致像这样的 DSL（我使用名称 DslOp 来表示操作，使用 Dsl 来表示生成的自由 monad）：

import cats.free.Free
import cats.free.Free.liftF

sealed trait DslOp[A]
case class Get[A](name: String) extends DslOp[A]

type Dsl[A] = Free[DslOp, A]
def get[A](name: String): Dsl[A] = liftF[DslOp, A](Get[A](name))

它定义了一个命令get，它可以在给定字符串的情况下获取A类型的对象名字.

稍后，您想使用某些 Client 提供的 get 方法来解释此 DSL 你不能修改：

import scala.concurrent.Future

trait Resource
trait Format[A <: Resource]
trait Definition[A <: Resource]

object Client {
  def get[A <: Resource](name: String)
    (implicit f: Format[A], d: Definition[A]): Future[A] = ???
}

您的问题是 Client 的 get 方法具有类型绑定，并且它需要额外的暗示。

为 Free monad 定义解释器时处理隐式

让我们首先假设客户端中的 get-方法需要隐式，但是暂时忽略绑定的类型：

import scala.concurrent.Future

trait Format[A]
trait Definition[A]

object Client {
  def get[A](name: String)(implicit f: Format[A], d: Definition[A])
  : Future[A] = ???
}

在我们写下解决方案之前，让我们简单讨论一下为什么你不能提供所有的在 ~>.

中调用 apply 方法时必要的隐式

传给foldMap时，FunctionK的apply应该是能够处理 Dsl[X] 类型的任意长程序以生成 Future[X]。
Dsl[X] 类型的任意长程序可以包含无限数量的 get[T1], ..., get[Tn] 不同类型的命令 T1, ..., Tn。
对于每个 T1, ..., Tn，您必须在某处获得 Format[T_i] 和 Definition[T_i]。
这些隐式参数必须由编译器提供。
当您解释整个 Dsl[X] 类型的程序时，只解释 X 类型，而不解释 T1, ..., Tn 可用，因此编译器无法在调用站点插入所有必需的 Definitions 和 Formats。
因此，所有 Definitions 和 Formats 必须作为隐式参数提供给 get[T_i] 当您构建 Dsl-程序时，而不是当您解释它时。

解决方案是将 Format[A] 和 Definition[A] 作为成员添加到 Get[A] 案例中 class，并使 get[A] 和 lift[DslOp, A] 的定义接受这两个额外的隐式参数：

import cats.free.Free
import cats.free.Free.liftF
import cats.~>

sealed trait DslOp[A]
case class Get[A](name: String, f: Format[A], d: Definition[A]) 
  extends DslOp[A]

type Dsl[A] = Free[DslOp, A]
def get[A](name: String)(implicit f: Format[A], d: Definition[A])
: Dsl[A] = liftF[DslOp, A](Get[A](name, f, d))

现在，我们可以定义 ~>-解释器的第一个近似值，它至少可以应对隐式：

val clientInterpreter_1: (DslOp ~> Future) = new (DslOp ~> Future) {
  def apply[A](op: DslOp[A]): Future[A] = op match {
    case Get(name, f, d) => Client.get(name)(f, d)
  }
}

类型范围以防 classes 定义 DSL-operations

现在，让我们单独处理绑定的类型。假设你的 Client 不需要任何隐式，但对 A:

施加了额外的限制

import scala.concurrent.Future

trait Resource
object Client {
  def get[A <: Resource](name: String): Future[A] = ???
}

如果您尝试以与在前面的示例中，您会注意到类型 A 太笼统了，而且因此，您无法在 Client.get 中使用 Get[A] 的内容。相反，你必须找到附加类型信息所在的范围 A <: Resource 没有丢失。实现它的一种方法是在 Get 本身上定义一个 accept 方法。而不是完全一般的自然变换 ~>，这个 accept 方法将能够使用 受限域 的自然变换。这是建模的特征：

trait RestrictedNat[R, F[_ <: R], G[_]] {
  def apply[A <: R](fa: F[A]): G[A]
}

它看起来几乎像 ~>，但有一个额外的 A <: R 限制。现在我们可以定义 accept in Get:

import cats.free.Free
import cats.free.Free.liftF
import cats.~>

sealed trait DslOp[A]
case class Get[A <: Resource](name: String) extends DslOp[A] {
  def accept[G[_]](f: RestrictedNat[Resource, Get, G]): G[A] = f(this)
}

type Dsl[A] = Free[DslOp, A]
def get[A <: Resource](name: String): Dsl[A] = 
  liftF[DslOp, A](Get[A](name))

并写下我们的解释器的第二个近似值，没有任何讨厌 type-casts:

val clientInterpreter_2: (DslOp ~> Future) = new (DslOp ~> Future) {
  def apply[A](op: DslOp[A]): Future[A] = op match {
    case g @ Get(name) => {
      val f = new RestrictedNat[Resource, Get, Future] {
        def apply[X <: Resource](g: Get[X]): Future[X] = Client.get(g.name)
      }
      g.accept(f)
    }
  }
}

这个想法可以推广到任意数量的类型构造函数 Get_1, ..., Get_N，具有类型限制 R1，...，RN。总体思路对应于从较小的分段定义的自然变换的构造仅适用于某些子类型的作品。

将两种解决策略应用到您的问题中

现在我们可以将两种通用策略合并为一个解决方案您的具体问题：

import scala.concurrent.Future
import cats.free.Free
import cats.free.Free.liftF
import cats.~>

// Client-definition with both obstacles: implicits + type bound
trait Resource
trait Format[A <: Resource]
trait Definition[A <: Resource]

object Client {
  def get[A <: Resource](name: String)
    (implicit fmt: Format[A], dfn: Definition[A])
  : Future[A] = ???
}


// Solution:
trait RestrictedNat[R, F[_ <: R], G[_]] {
  def apply[A <: R](fa: F[A]): G[A]
}

sealed trait DslOp[A]
case class Get[A <: Resource](
  name: String,
  fmt: Format[A],
  dfn: Definition[A]
) extends DslOp[A] {
  def accept[G[_]](f: RestrictedNat[Resource, Get, G]): G[A] = f(this)
}

type Dsl[A] = Free[DslOp, A]
def get[A <: Resource]
  (name: String)
  (implicit fmt: Format[A], dfn: Definition[A])
: Dsl[A] = liftF[DslOp, A](Get[A](name, fmt, dfn))


val clientInterpreter_3: (DslOp ~> Future) = new (DslOp ~> Future) {
  def apply[A](op: DslOp[A]): Future[A] = op match {
    case g: Get[A] => {
      val f = new RestrictedNat[Resource, Get, Future] {
        def apply[X <: Resource](g: Get[X]): Future[X] = 
          Client.get(g.name)(g.fmt, g.dfn)
      }
      g.accept(f)
    }
  }
}

现在，clientInterpreter_3可以解决这两个问题：type-bound-problem可以解决通过为每个案例 class 定义一个 RestrictedNat 对其类型参数施加上限， implicits-problem 通过向 DSL 的 get 方法添加隐式参数列表来解决。

Answer 2

我想我找到了一种方法来解决您的问题，方法是结合 ReaderT monad transformer with intersection types:

import scala.concurrent.Future
import cats.~>
import cats.data.ReaderT
import cats.free.Free

object FreeMonads {
  sealed trait Op[A]

  object Op {
    final case class Get[T](name: String) extends Op[T]
    type OpF[A] = Free[Op, A]
    def get[T](name: String): OpF[T] = Free.liftF[Op, T](Get[T](name))
  }

  trait Resource
  trait Format[A]
  trait Definition[A]

  trait Client {
    def get[O <: Resource](name: String)
      (implicit f: Format[O], d: Definition[O]): Future[O]
  }

  type Result[A] = ReaderT[
    Future,
    (Format[A with Resource], Definition[A with Resource]),
    A,
  ]

  class FutureOp(client: Client) extends (Op ~> Result) {
    def apply[A](fa: Op[A]): Result[A] =
      fa match {
        case Op.Get(name: String) =>
          ReaderT {
            case (format, definition) =>
              // The `Future[A]` type ascription makes Intellij IDEA's type
              // checker accept the code.
              client.get(name)(format, definition): Future[A]
          }
      }
  }
}

其背后的基本思想是您从 Op 生成一个 Reader 并且 Reader 接收可用于隐式参数的值。这解决了类型 O 具有 Format 和 Definition.

实例的问题

另一个问题是 O 是 Resource 的子类型。为了解决这个问题，我们只是说 Format 和 Definition 实例不仅是任何 A 的实例，而且任何 A 也恰好是 Resource.

如果您在使用 FutureOp 时遇到问题，请告诉我。

FunctionK 类型参数的界限

Bounds for type parameter of FunctionK

scala

scala-cats

设置

为 Free monad 定义解释器时处理隐式

类型范围以防 classes 定义 DSL-operations

将两种解决策略应用到您的问题中