scala - 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

（我的原始答案包含相同的想法，但是显然它没有提供足够的实现细节。这一次，我编写了更详细的分步指南，其中讨论了每个中间步骤。每个部分都包含一个单独的可编译代码段。 ）



TL; DR


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




在您的问题中，您有两个独立的问题：


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


我想单独对待这两个问题，并为这两个问题提供可重用的解决方案。然后，我将两种策略都应用于您的问题。

我的回答如下：


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


此后，我假设您具有scalaVersion 2.12.4，即依赖项

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

然后您插入

import scala.language.higherKinds

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



设置

本部分的目的是确保我正在解决正确的问题，并提供非常简单的模型定义
Resource， Format， Client等的形式，因此该答案是独立的
并且可编译。

我假设您想使用 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的对象
名称。

稍后，您想使用某些 get提供的 Client方法解释此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] = ???
}

您的问题是 get的 Client方法具有类型绑定，并且
它需要其他隐式。

为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时，应假定 apply的 FunctionK
以便能够处理 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可用，
因此，编译器无法在调用站点插入所有必需的 Definition和 Format。
因此，必须将所有 Definition和 Format作为隐式参数提供给 get[T_i]
在构造 Dsl程序时，而不是在解释它时。


解决方案是将 Format[A]和 Definition[A]作为成员添加到 Get[A]案例类中，
并使 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)
  }
}

定义DSL操作的案例类的类型界限

现在，让我们处理隔离绑定的类型。假设您的 Client
不需要任何隐式，但在 A上附加了一个附加限制：

import scala.concurrent.Future

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

如果您尝试以与
在前面的示例中，您会注意到类型 clientInterpreter过于笼统，并且
因此，您不能使用 A中 Get[A]的内容。
相反，您必须找到一个范围，其中其他类型信息 Client.get
没有丢失。一种实现方法是在 A <: Resource本身上定义 accept方法。
代替完全普通的自然变换 Get，此 ~>方法将
能够处理具有受限域的自然转换。
这是要建模的特征：

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

它看起来几乎像 accept，但有一个附加的 ~>限制。现在我们
可以在 A <: R中定义 accept：

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))

并写下我们翻译的第二种近似
讨厌的类型转换：

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，...，
Get_1，类型限制为 Get_N，...， R1。总体思路对应于
由较小的分段定义的自然变换的构造
仅适用于某些子类型的片段。

将两种解决方案策略都应用于您的问题

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

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)
    }
  }
}

现在， RN可以解决两个问题：处理类型绑定问题
通过为每个案例类定义一个 clientInterpreter_3并为其类型参数加上上限的方式，
通过将隐式参数列表添加到DSL的 RestrictedNat方法中，可以解决隐式问题。