Scala 扁平化深度函数混淆

Question

我对有关提供的 function/with 使用示例的文档感到有点困惑。 flatten 只能发生一次吗？喜欢

List(List(1, 2), List(3, List(4, 5, 6))) -> List(1, 2, 3, List(4, 5, 6))

或者您以某种方式指定展平的深度，使其成为 List(1, 2, 3, 4, 5, 6) ?

因为，例如，在 JS 中，函数似乎可以 flat() 任何你想要的一维数组深度。 Scala flatten 可以做到这一点还是只能提升一次？

我正在尝试自己重新创建该功能，并想模仿所需的行为并了解其工作方式可能不同的原因。

Answer 1

如注释中所述，在 Scala 2 中定义此类方法并非以类型安全的方式直接进行。首先，Scala 2 不直接支持递归类型，因此您必须对 List[Any] 进行操作，并使用运行时反射来区分元素是列表还是整数。

最近发布的Scala 3在类型系统上有很多改进，所以我想知道是否可以在那里实现这样的方法？我试过了，我认为我能够实现可用的实现。

首先，我想知道是否可以实现递归联合类型（打字稿中可能有类似的事情）：

type ListOr[A] = A | List[ListOr[A]]

不幸的是，这种类型引发了编译器错误：

illegal cyclic type reference: alias ... of type ListOr refers back to the type itself

真令人失望，but after some digging，我发现我可以定义这样的递归类型：

type ListOr[A] = A match {
  case AnyVal => AnyVal | List[ListOr[AnyVal]]
  case _ => A | List[ListOr[A]] 
}

并且可用：

val ints: ListOr[Int] = List(List(1), 2, 3, List(List(4, List(5)), 6), 7, 8, List(9))

val strings: ListOr[String] = List(List("A", "B", "C"), List(List("D", List("E")), "F"), "G", "H", List("I"), "J")

所以现在我只需要实现展平功能：

//I needed class tag for A to be able to do a match
def deepFlatten[A: ClassTag](s: ListOr[A]): List[A] =
  s match 
    case a: A => List(a)
    case ls: List[_ <: ListOr[A]] => ls.flatMap(deepFlatten(_))

它似乎工作正常：

@main
def main = 
  val i: List[Int] = deepFlatten[Int](ints) //List(1, 2, 3, 4, 5, 6, 7, 8, 9)
  val j: List[String] = deepFlatten[String](strings)//List(A, B, C, D, E, F, G, H, I, J)

显然，这种实现可以改进（它不是尾递归），但它正在发挥作用。

由于我是 Scala 3 的新手，我不确定这是否是最好的实现，但绝对可以实现类型安全的任意深度扁平化函数。

Scastie with the solution.

Answer 2

这是尝试使用简单的 Tree 数据结构来做类似的事情。

final case class Tree[+A](value: A, children: List[Tree[A]] = Nil)

def flattenTree[A](tree: Tree[A]): List[A] = {
  @annotation.tailrec
  def loop(remainingNodes: List[Tree[A]], acc: List[A]): List[A] =
    remainingNodes match {
      case Tree(value, children) :: tail =>
        loop(
          remainingNodes = children reverse_::: tail,
          value :: acc
        )
      
      case Nil =>
        acc
    }
  
  loop(remainingNodes = tree :: Nil, acc = List.empty)
}

可以这样使用：

val tree = Tree(
  value = 1,
  children = List(
    Tree(value = 2),
    Tree(
      value = 3,
      children = List(
        Tree(value = 4),
        Tree(value = 5),
        Tree(value = 6)
      )
    )
  )
)

val flattenedTree = flattenTree(tree)
println(flattenedTree.mkString("[", ", ", "]"))

这将产生以下输出：

[2, 4, 5, 6, 3, 1]

如您所见，是一个反转的 DFS （其结果也是反转的）。如果顺序无关紧要，这是一种直接而有效的实现方式，如果顺序很重要，那么可以使用代码。

另一种方法是使用如下数据结构：

sealed trait ListOr[+A] extends Product with Serializable
final case class NestedList[+A](data: List[ListOr[A]]) extends ListOr[A]
final case class SingleValue[+A](value: A) extends ListOr[A]

可以看到代码运行 here.

Scala 扁平化深度函数混淆

Scala flatten depth function confusion

scala

scala-collections

iterable

flatten