如何创建可以从任意深度嵌套的列表中生成平面列表的函数？

Question

是否可以在 scala 中编写函数，将任意深度嵌套列表的列表递归地转换为平面列表？例如：

flatten(List(List(1), List(List(2), 3), 4))

应该return

List(1,2,3,4)

我用 shapeless 做了一些尝试，但没有效果：

object flatten extends (List ~> List) {
    def apply[T](s: List[T]) = s.map {
       case l: List[T] => apply(s)
       case x => x
    }
}

这给了我：

type mismatch

found: List[Any]

required: List[T]

如果能扣除正确的类型也很好（例如List[Int]而不是List[Any]）

Answer 1

问题是，您在输入中没有收到 List[T]，而是 List[Any]，其中 Any 是 T 和 [=12= 的混合].

因此，如果您知道叶元素的类型，则可以通过在 T 或 List[Any] 上递归模式匹配来使用类型参数 T 来表示它和平面图元素:

import scala.reflect.ClassTag

def flatten[T: ClassTag](list: List[Any]): List[T] =
  list.flatMap {
    case x: T => List(x)
    case sub: List[Any] => flatten[T](sub)
  }

flatten[Int](List(List(1), List(List(2), 3), 4))
// List[Int] = List(1, 2, 3, 4)

Answer 2

您想要的 flatten 本质上是无类型的。您正在放置元素（假设它们的类型为 E）、其列表 (List[E])、列表 thereof (List[List[E]]) 等。到一个列表中，该列表必须具有 List[Any] 类型，因为它的元素没有任何共同点。 Shapeless 就是关于拥有描述性类型并在它们之间进行转换，因此它对您没有任何帮助。此外，查看您的函数定义：

def apply[T](s: List[T]) = s.flatMap { // should be flatMap, conceptually
   case l: List[T] => apply(l) // should be l, conceptually
   case x => List(x) // should be singleton list, conceptually
}

因此，s 是一个 List[T]，而 s.map 依次为您提供每个 T。然后，您使用一个类型 case，并且在其中一个臂中，您检查 l: T 是否实际上是一个 l: List[T]。也就是说，您检查 List[T] <: T。这很奇怪，表示您的功能不正确。

如果您真的想使用 Shapeless，请使用类型准确描述您的输入。我们想要这个接口 flatten[T]:

如果它收到 t: T，那么它 returns List(t): List[T]。
如果它接收到 l: List[X]，其中 X 是 flatten[T] 的有效输入，它会展平每个 X，然后将结果的串联输出为一个, 大 List[T].
如果它接收到 h: H，其中 H <: HList，其中 H 的每个元素都是 flatten[T] 的有效输入，每个元素都被展平，结果被连接起来合并成 List[T].

这是它的实现：

object flatten extends Poly1 {
  implicit def caseT[T] = at[T](List(_))
  implicit def caseList[T, X](implicit e: Case.Aux[X, List[T]])
    = at[List[X]](_.flatMap(e))
  implicit def caseHNil[T, N <: HNil] = at[N](_ => List[T]())
  implicit def caseHCons[T, H, R <: HList](implicit hf: Case.Aux[H, List[T]],
                                                    rf: Case.Aux[R, List[T]])
    = at[H :: R] { case h :: r => hf(h) ++ rf(r) }

  final class Specialized[T] {
    def apply[X](x: X)(implicit c: Case.Aux[X, List[T]]): List[T] = c(x)
  }
  def apply[T]: Specialized[T] = new Specialized
}

使用情况：

scala> flatten[Int]((1 :: HNil) :: ((2 :: HNil) :: 3 :: HNil) :: 4 :: HNil)
List(1, 2, 3, 4)
scala> flatten[Int](1 :: List(2, 3) :: List(List(4, 5), List(), List(6, 7)) :: List(8 :: List(9, 10) :: HNil, 11 :: List(12, 13, 14) :: HNil) :: HNil)
List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)

另一种方法是简单地使用正确的数据结构。在这种情况下，正确的结构称为 List 上的自由 monad，也称为玫瑰树：

sealed trait Free[M[+_], +A] {
  def flatten(implicit M: Monad[M]): M[A]
}
case class Pure[M[+_], +A](x: A) extends Free[M, A] {
  override def flatten(implicit M: Monad[M]) = M.pure(x)
}
case class Step[M[+_], +A](step: M[Free[M, A]]) extends Free[M, A] {
  override def flatten(implicit M: Monad[M]) = step.flatMap(_.flatten)
}
// for convenience
object Rose {
  type Rose[+A] = Free[List, A]
  type Leaf[+A] = Pure[List, A]
  type Branch[+A] = Step[List, A]
  object Leaf {
    def apply[A](x: A): Leaf[A] = Pure(x)
    def unapply[A](x: Leaf[A]): Some[A] = Some(x.x)
  }
  object Branch {
    def apply[A](xs: Rose[A]*): Branch[A] = Step(xs.toList)
    def unapplySeq[A](xs: Branch[A]): Some[List[Rose[A]]] = Some(xs.step)
  }
}
// specialized:
// sealed trait Rose[+A] { def flatten: List[A] }
// case class Leaf[+A](x: A) extends Rose[A] { override def flatten = List(x) }
// case class Branch[+A](x: List[Rose[A]]) extends Rose[A] { override def flatten = x.flatMap(_.flatten) }

用法：

scala> Branch(Branch(Leaf(1)), Branch(Branch(Leaf(2)), Leaf(3)), Leaf(4)).flatten

如何创建可以从任意深度嵌套的列表中生成平面列表的函数？

How to create function which would make flat List from arbitrarily deeply nested lists?

scala

shapeless