将无序的HList转换为更小的HList

Question

我有一个没有固定形状的HList，其结构如下：

type ABCAB = List[A] :: List[B] :: List[C] :: List[A] :: List[B] :: HNil
val abcab: ABCAB = List[A]() :: List(B) :: List[C]() :: List(A) :: List(B) :: HNil

我希望您能够将其转换为更简单的类型，其中相同类型的列表会从左到右进行追加。

type ABC = List[A] :: List[B] :: List[C] :: HNil        
val abc: ABC = abcab.magic                       // does magic exist in shapeless?
abc == List(A) :: List(B,B) :: List[C]() :: HNil // true

有没有shapeless v1.2.4中的内置功能可以实现这个？

- ahjohannessen

---

不，你可以在这里找到所有的函数 https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/ops/hlists.scala 你必须编写自己的 magic 函数，我现在完全没有时间，也许稍后我会发布一个解决方案，或者其他人会发布。 - DaunnC

@DaunnC 好的。谢谢，那会很有帮助。 - ahjohannessen

Answer 1

虽然其他答案所采取的方法（引入新的类型类）是可行的，但是我们可以使用更一般性的机制来解决这个问题——而且解决方式与在值层面解决类似问题的方式并没有太大区别。

我们将使用左折叠。编写组合函数有点棘手，因为我们有两种情况（我们已经看到了与当前元素相同类型的元素，或者我们还没有），我们必须使用隐式优先级技巧来避免模糊的隐式值：

import shapeless._

trait LowPriorityCombine extends Poly2 {
  implicit def notAlreadySeen[L <: HList, A](implicit
    p: Prepend[L, List[A] :: HNil]
  ) = at[L, List[A]](_ :+ _)
}

object combine extends LowPriorityCombine {
  implicit def alreadySeen[L <: HList, A](implicit
    s: Selector[L, List[A]],
    r: Replacer[L, List[A], List[A]]
  ) = at[L, List[A]] {
    case (acc, as) => acc.updatedElem[List[A]](acc.select[List[A]] ++ as)
  }
}

但是，我们基本上已经完成了：

def magic[L <: HList](l: L)(implicit f: LeftFolder[L, HNil.type, combine.type]) =
  l.foldLeft(HNil)(combine)

我们可以展示它的工作原理：

val xs = List(1, 2, 3) :: List('a, 'b) :: List("X", "Y") :: List(4, 5) :: HNil
val test = magic(xs)

然后：

scala> test == List(1, 2, 3, 4, 5) :: List('a, 'b) :: List("X", "Y") :: HNil
res0: Boolean = true

正如预期的一样。

上面的代码是针对1.2.4编写的，但只需进行一些非常小的修改即可在2.0上工作。

---

更新：为了记录，这里提供适用于2.0版本的可工作版本：

import shapeless._, ops.hlist.{ LeftFolder, Prepend, Replacer, Selector }

trait LowPriorityCombine extends Poly2 {
  implicit def notAlreadySeen[L <: HList, A, Out <: HList](implicit
    p: Prepend.Aux[L, List[A] :: HNil, Out]
  ): Case.Aux[L, List[A], Out] = at[L, List[A]](_ :+ _)
}

object combine extends LowPriorityCombine {
  implicit def alreadySeen[L <: HList, A, Out <: HList](implicit
    s: Selector[L, List[A]],
    r: Replacer.Aux[L, List[A], List[A], (List[A], Out)]
  ): Case.Aux[L, List[A], Out] = at[L, List[A]] {
    case (acc, as) => acc.updatedElem[List[A], Out](acc.select[List[A]] ++ as)
  }
}

def magic[L <: HList](l: L)(implicit f: LeftFolder[L, HNil, combine.type]) =
  l.foldLeft(HNil: HNil)(combine)

主要区别在于新的导入，但由于updatedElem上额外的类型参数，您还需要进行其他一些小的更改。

- Travis Brown

---

我想知道你的解决方案是否可以推广到使用Monoid方法，以便它适用于除List之外的其他事物？ :) - ahjohannessen

@ahjohannessen：当然可以！对于“combine”的更改将非常简单。 - Travis Brown

谢谢更新 :) 所以诀窍是通过类型参数传播 Out 并使用 Aux。 - ahjohannessen

Travis，似乎我在LeftFolder缺少隐式的错误。你验证过这个例子是否有效吗？ - ahjohannessen

已确认在2.11.1上也能够与2.0.0版本兼容。 - Travis Brown

Answer 2

本文实现适用于 shapeless 2.0，但是进行轻微修改后也可适用于 1.2.4:

import shapeless._

// remove this import for v1.2.4
import shapeless.ops.hlist.{Filter, FilterNot, RightReducer}

// for v1.2.4 replace `Poly` with `Poly2` and `use` with `at`
object combine extends Poly {
  implicit def lists[T] = use((c : List[T], s : List[T]) => c ::: s)
}

trait ListGroup[In <: HList] {
  type Out <: HList
  def apply(l: In): Out
}

object ListGroup {
  implicit def hnil =
    new ListGroup[HNil] {
      type Out = HNil
      def apply(l: HNil) = l
    }

  implicit def hlist[T, Tail <: HList, NOut <: HList, F <: HList, Rest <: HList](
                 implicit f: Filter[List[T] :: Tail, List[T]] { type Out = F },
                          r: RightReducer[F, combine.type] { type Out = List[T] },
                          fn: FilterNot[List[T] :: Tail, List[T]] { type Out = Rest },
                          next: ListGroup[Rest] { type Out = NOut }) =
    new ListGroup[List[T] :: Tail] {
      type Out = List[T] :: NOut
      def apply(l: List[T] :: Tail): List[T] :: NOut =
        l.filter[List[T]].reduceRight(combine) :: next(l.filterNot[List[T]])
    }
}

def magic[L <: HList](l: L)(implicit g: ListGroup[L]) = g(l)

使用方法：

val hl = List(1, 2, 3) :: List('a, 'b) :: List("aa", "bb", "cc") :: List(4, 5) :: List('c, 'd, 'e) :: HNil

magic(hl)
// List(1, 2, 3, 4, 5) :: List('a, 'b, 'c, 'd, 'e) :: List(aa, bb, cc) :: HNil

对于 v1.2.4 版本，请替换 combine 对象，使用此实现：

object combine extends Poly2 {
  implicit def lists[T] = at((c : List[T], s : List[T]) => c ::: s)
}

- senia

---

非常感谢 @senia :) 我会尝试一下。 - ahjohannessen