链接通过最短路径牵连

Question

问题

我有一组类型和一组转换.这听起来像DAG并且与它有一些相似之处.如果可行,我希望能够在任意两种类型之间计算隐式最短的转换路径.

我准备了一个简单的例子,表明我徒劳地试图宣布这样的含义.

final case class A(u : Int)
final case class B(u : Int)
final case class BB(u : Int)
final case class C(u : Int)
final case class D(u: Int)

trait Convert[F,T] {
  def convert(source : F) : T
}

我介绍以下测试用例转化:A - > B,A - > BB,B - > C,B - > d,C - > d.

我尝试了两种方法,它们给了我不同的隐式分辨率错误.

过境链

trait ConcreteConvert[F,T] extends Convert[F,T]

class Transit[F,M,T](implicit fm : ConcreteConvert[F,M], mt : Convert[M,T]) extends Convert[F,T] {
  override def convert(source : F) : T =
    mt.convert( fm.convert(source) )
}

object Implicits {
  implicit def transit[F,M,T](implicit fm : ConcreteConvert[F,M], mt : Convert[M,T]) : Convert[F,T] =
    new Transit()(fm, mt)

  implicit object A2B extends ConcreteConvert[A,B] {
    override def convert(source : A) : B = B(source.u)
  }
  implicit object B2C extends ConcreteConvert[B,C] {
    override def convert(source : B) : C = C(source.u)
  }
  /*implicit object A2BB extends ConcreteConvert[A,BB] {
    override def convert(source : A) : BB = BB(source.u)
   }*/ // compilation fails
  implicit object C2D extends ConcreteConvert[C,D] {
    override def convert(source : C) : D = D(source.u)
  }
  implicit object B2D extends ConcreteConvert[B,D] {
    override def convert(source : B) : D = D(source.u)
  }
}

object Usage {
  import Implicits._
  def conv[F,T](source : F)(implicit ev : Convert[F,T]) : T =
    ev.convert(source)

  val a = A(0)
  val b = conv[A,B](a)
  val c = conv[A,C](a)
  val d = conv[A,D](a)
}

这种方法使得A - > B - > C - > D和A - > B - > D之间的路径分辨率成为可能,编译器选择后一种路径.但如果有任何分支,它就会失败

继续传球

abstract class PostConvert[F, M, T](mt : Convert[M,T]) extends Convert[F,T] {
  def pre(source : F) : M

  override def convert(source : F) : T =
    mt.convert( pre(source) )
}

class IdConvert[F]() extends Convert[F,F] {
  override def convert(source : F) : F =
    source
}

object ImplicitsPost {
  implicit def idConvert[F] : Convert[F,F] =
    new IdConvert[F]()

  implicit def a2b[T](implicit mt : Convert[B,T]) = new PostConvert[A,B,T](mt) {
    override def pre(source : A) : B = B(source.u)
  }
  implicit def a2bb[T](implicit mt : Convert[BB,T]) = new PostConvert[A,BB,T](mt) {
    override def pre(source : A) : BB = BB(source.u)
  }
  implicit def b2c[T](implicit mt : Convert[C,T]) = new PostConvert[B,C,T](mt) {
    override def pre(source : B) : C = C(source.u)
  }
  implicit def c2d[T](implicit mt : Convert[D,T]) = new PostConvert[C,D,T](mt) {
    override def pre(source : C) : D = D(source.u)
  }
  /*implicit def b2d[T](implicit mt : Convert[D,T]) = new PostConvert[B,D,T](mt) {
    override def pre(source : B) : D  = D(source.u)
  }*/ // compiler fails
}

object UsagePost {
  import ImplicitsPost._
  def conv[F,T](source : F)(implicit ev : Convert[F,T]) : T =
    ev.convert(source)

  val a = A(0)
  val b = conv[A,B](a)
  val c = conv[A,C](a)
  val d = conv[A,D](a)
}

在这种情况下,编译器可以忽略不相关的A - > BB转换.但它无法解决冲突A - > B - > C - > D和A - > B - > D.

我正在寻找什么

以通用方式解决问题的一些方法.我可以定义关系图并让隐式机制选择其中的最短路径.如果我可以调整每个转换权重以使A - > B - > D和A - > C - > D可区分,那会更好.隐式解决方案优先级背后有一些黑魔法,我希望它可以提供帮助.

Implicits据说是非常强大的计算工具,几分钟的编译器工作在复杂的情况下值得.因此,我希望通过一些棘手的技术可以进行任意长传递转换.

Answer 1

\n\n

简短回答

\n\n

在当前的措辞中，你无法使用 scala 隐式解析来解决这个问题，因为它不支持回溯。

\n\n

实用答案

\n\n

您最好的选择可能是修改 scala 编译器以支持隐式解析中的回溯，这应该足以让您的第一个实现正常工作。

\n\n

长答案

\n\n

我撒谎了，在编译器的当前状态下应该是可能的，但它不会像您编写的等效 Prolog 程序那么好，并且可能超出了“哦，这应该很有趣”的范围在类型级别编写”；)。让我首先重新表述一下你的问题。

\n\n

给出几种类型：

\n\n

trait A; trait B; trait B; trait C; trait D\n

\n\n

以及这些类型的有向图：

\n\n

trait Edge[X, Y]\n\ndef fact[X, Y] = new Edge[X, Y] {}\n\nimplicit val edge0: Edge[A, B]  = fact //   ( A )\nimplicit val edge1: Edge[A, BB] = fact //   \xe2\x86\x93   \xe2\x86\x93\nimplicit val edge2: Edge[B, C]  = fact // ( B ) BB\nimplicit val edge3: Edge[B, D]  = fact // \xe2\x86\x93   \xe2\x86\x93\nimplicit val edge4: Edge[C, D]  = fact // C \xe2\x86\x92 D\n

\n\n

A使用隐式解析找到和之间的最短路径D。

\n\n

要了解这个问题的棘手之处，将其分解为两部分会很有用：

\n\n

\n

1. 将它们提升implicit edges为从节点开始的图的类型级别表示A，如下所示：

   \n\n

   A \n  :: (B\n    :: (C :: (D :: HNil) :: HNil)\n    :: (D :: HNil)\n    :: HNil)\n  :: (BB :: HNil)\n  :: HNil\n

\n

2. 对此表示执行类型级别 BFS。

\n

\n\n

令人惊讶的是，1. 听起来更棘手，这是因为 scala 隐式解析不进行回溯。为了实现这一点，您必须采用稍微不同的图表表示形式。

\n\n

一种坚持原始公式（每条边隐式）的解决方案可能是使用与本示例中公开的技术类似的技术，该技术使用两个trait EdgeLeft[X, Y]&trait EdgeRight[X, Y]而不是 a trait Edge[X, Y]，并将图形的所有边HList有效地收集到单个边中解决缺乏回溯的问题。

\n\n

您还可以通过以更接近邻接矩阵的表示形式对图形进行编码，例如使用implicit fact: Neighbours[A, B :: BB :: HNil]. 但无论哪种方式，对图形表示的轻微更改应该足以让您构建与上述图形表示等效的结构。

\n\n

解决 2. 并不容易，但理论上应该不会比在以下输入上编写纯值级别 DFS 并将其提升到类型级别更难：

\n\n

val input: List[Any] = (\n  "A" \n    :: ("B"\n      :: ("C" :: ("D" :: Nil) :: Nil)\n      :: ("D" :: Nil)\n      :: Nil)\n    :: ("BB" :: Nil)\n    :: Nil\n)\n\ndef DFS(i: List[Any]): List[String] = ???\n

\n