Scala展平深度函数混淆

Question

我对有关此功能的文档/提供的使用示例感到有些困惑。是否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]]

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

非法循环类型引用：别名 ... 类型 ListOr 指回类型本身

这令人失望，但经过一番挖掘后，我发现我可以将这样的递归类型定义为：

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 的解决方案。