无形-副产品中的重复数据删除类型

Question

鉴于我有一种类型Int :+: Int :+: String :+: CNil，是否有简单的方法可以将其转换为Int :+: String :+: CNil？

Answer 1

这取决于您所说的“简单”。我很确定没有简单的方法可以通过构成Shapeless中可用的副产品操作来执行此操作，但是编写自己的类型类来做到这一点相当简单（至少就这些事情而言） 。

我将假设您的要求中未指定的几件事：

1. 您希望生成的副产品中的类型是唯一的（例如，您不像示例中那样折叠相邻的元素）。
2. 对于非相邻重复类型，您希望最后一个重复包含在结果中。

如果这些假设不正确的话，在下面调整解决方案将不会太困难，其核心思想是相同的。

完整的解决方案如下所示：

import shapeless.{ :+:, CNil, Coproduct, DepFn1, Inl, Inr }
import shapeless.ops.coproduct.Inject

trait Unique[C <: Coproduct] extends DepFn1[C] {
  type Out <: Coproduct
}

object Unique extends LowPriorityUnique {
  type Aux[C <: Coproduct, Out0 <: Coproduct] = Unique[C] { type Out = Out0 }

  def apply[C <: Coproduct](implicit unC: Unique[C]): Aux[C, unC.Out] = unC

  implicit val uniqueCNil: Aux[CNil, CNil] = new Unique[CNil] {
    type Out = CNil
    def apply(c: CNil): CNil = c
  }

  implicit def uniqueCCons1[L, R <: Coproduct](implicit
    inj: Inject[R, L],
    unR: Unique[R]
  ): Aux[L :+: R, unR.Out] = new Unique[L :+: R] {
    type Out = unR.Out

    def apply(c: L :+: R): unR.Out = unR(
      c match {
        case Inl(l) => inj(l)
        case Inr(r) => r
      }
    )
  }
}

class LowPriorityUnique {
  implicit def uniqueCCons0[L, R <: Coproduct](implicit
    unR: Unique[R]
  ): Unique[L :+: R] { type Out = L :+: unR.Out } = new Unique[L :+: R] {
    type Out = L :+: unR.Out

    def apply(c: L :+: R): L :+: unR.Out = c match {
      case Inl(l) => Inl(l)
      case Inr(r) => Inr(unR(r))
    }
  }
}

我们可以逐步完成此代码。

trait Unique[C <: Coproduct] extends DepFn1[C] {
  type Out <: Coproduct
}

这是我们的类型类。它表征了一个副产品C，并且在任何情况下，其输出类型都是唯一的C，而该输出类型也是一个副产品。从中DepFn1我们得到一个方法apply，该方法取a C并返回a Out；这就是我们将在下面的实例中实现的内容。

在伴随对象中，我们有几行基本上是样板式的—并非严格必要，但它们支持此类型类的方便，惯用用法：

type Aux[C <: Coproduct, Out0 <: Coproduct] = Unique[C] { type Out = Out0 }

def apply[C <: Coproduct](implicit unC: Unique[C]): Aux[C, unC.Out] = unC

第一行让我们避免Foo[X] { type Bar = Bar0 }在任何地方都写类型细化（），第二行让我们Unique[C]代替进行写入implicitly[Unique[C]]（并且还返回经过细化的结果而不是无用的unrefined Unique[C]）。

接下来，我们有基本情况：

implicit val uniqueCNil: Aux[CNil, CNil] = new Unique[CNil] {
  type Out = CNil
  def apply(c: CNil): CNil = c
}

这很简单：如果我们得到一个空的副产品，我们知道它的元素已经是唯一的。

接下来，我们有几个归纳案例。第一个uniqueCCons1覆盖副产品的头部位于尾部uniqueCCons0的情况，第二个覆盖副产品的头部不在尾部的情况。因为uniqueCCons1适用于部分案例uniqueCCons0涵盖，所以我们必须明确地确定这两个实例的优先级。我使用子类来uniqueCCons0降低优先级，因为我认为这是最简单的方法。

这两个实例的实现可能看起来有些混乱，但是逻辑实际上并不那么复杂。在这两种情况下，我们都有一个归纳Unique[R]实例。区别在于，在这种1情况下，我们首先将头部注入尾巴（依靠Shapeless的Injecttype类来见证L发生在中R），然后应用unR，在这种0情况下，我们仅将其应用于尾巴而头部保持不变。

它是这样的：

scala> type C = Int :+: String :+: CNil
defined type alias C

scala> Unique[C]
res0: Unique[Int :+: String :+: shapeless.CNil]{type Out = Int :+: String :+: shapeless.CNil} = LowPriorityUnique$$anon$3@2ef6f000

scala> Unique[C].apply(Inl(1))
res1: Int :+: String :+: shapeless.CNil = Inl(1)

scala> type C2 = Int :+: String :+: Int :+: CNil
defined type alias C2

scala> Unique[C2].apply(Inr(Inr(Inl(1))))
res2: String :+: Int :+: shapeless.CNil = Inr(Inl(1))

scala> Unique[C2].apply(Inl(1))
res3: String :+: Int :+: shapeless.CNil = Inr(Inl(1))

符合我们上面的要求。

Answer 2

这是一个简单的方法吗？

  import shapeless.{:+:, =:!=, CNil, Coproduct, Inl, Inr, unexpected}

  trait Deduplicate[C <: Coproduct] {
    type Out <: Coproduct
    def apply(c: C): Out
  }
  object Deduplicate {
    type Aux[C <: Coproduct, Out0 <: Coproduct] = Deduplicate[C] { type Out = Out0 }
    def instance[C <: Coproduct, Out0 <: Coproduct](f: C => Out0): Aux[C, Out0] = new Deduplicate[C] {
      override type Out = Out0
      override def apply(c: C): Out = f(c)
    }

    implicit def zero: Aux[CNil, CNil] = instance(_ => unexpected)
    implicit def one[H]: Aux[H :+: CNil, H :+: CNil] = instance(identity)
    implicit def duplicates[H, T <: Coproduct](implicit
      dedup: Deduplicate[H :+: T]): Aux[H :+: H :+: T, dedup.Out] = instance {
      case Inl(h) => dedup(Inl(h))
      case Inr(c) => dedup(c)
    }
    implicit def noDuplicates[H, H1, T <: Coproduct](implicit
      dedup: Deduplicate[H1 :+: T],
      ev1: H =:!= H1): Aux[H :+: H1 :+: T, H :+: dedup.Out] = instance {
      case Inl(h) => Inl(h)
      case Inr(c) => Inr(dedup(c))
    }
  }
  implicit class DeduplicateOps[C <: Coproduct](c: C) {
    def deduplicate(implicit dedup: Deduplicate[C]): dedup.Out = dedup(c)
  }

  implicitly[Deduplicate.Aux[String :+: Int :+: Int :+: String :+: String :+: CNil,
    String :+: Int :+: String :+: CNil]]