scala - 此递归列表展平如何工作？

Question

在Scala邮件列表上返回this was asked and answered:

凯文:

Given some nested structure: List[List[...List[T]]] what's the best (preferably type-safe) way to flatten it to a List[T]

杰斯珀:

A combination of implicits and default arguments works:

case class Flat[T, U](fn : T => List[U]) 

implicit def recFlattenFn[T, U](implicit f : Flat[T, U] = Flat((l : T) 
=> List(l))) = 
   Flat((l : List[T]) => l.flatMap(f.fn)) 

def recFlatten[T, U](l : List[T])(implicit f : Flat[List[T], U]) = f.fn(l) 

例子:

scala> recFlatten(List(1, 2, 3)) 
res0: List[Int] = List(1, 2, 3) 

scala> recFlatten(List(List(1, 2, 3), List(4, 5))) 
res1: List[Int] = List(1, 2, 3, 4, 5) 

scala> recFlatten(List(List(List(1, 2, 3), List(4, 5)), List(List(6, 7)))) 
res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7) 

我一直在看这段代码。我不知道它是如何工作的。似乎涉及到一些递归...有人可以阐明吗？还有其他这种模式的例子，它有名字吗？

Answer 1

哦，哇，这是旧的!我将首先清理一下代码并将其与当前的惯用惯例保持一致:

case class Flat[T, U](fn: T => List[U]) 

implicit def recFlattenFn[T, U](
  implicit f: Flat[T, U] = Flat((xs: T) => List(xs))
) = Flat((xs: List[T]) => xs flatMap f.fn)

def recFlatten[T, U](xs: List[T3])(implicit f: Flat[List[T], U]) = f fn xs 

然后，事不宜迟，分解代码。首先，我们有 Flat类:

case class Flat[T, U](fn: T => List[U]) 

这只不过是函数 T => List[U]的命名包装，该函数将在给定类型为 List[U]的实例时构建 T。请注意，此处的 T也可以是 List[U]或 U或 List[List[List[U]]]等。通常，此类函数可以直接指定为参数的类型。但是我们将在隐式中使用此方法，因此命名包装程序可以避免任何隐式冲突的风险。

然后，从 recFlatten向后工作:

def recFlatten[T, U](xs: List[T])(implicit f: Flat[List[T], U]) = f fn xs 

此方法将采用 xs(一个 List[T])并将其转换为 U。为此，它找到了 Flat[T,U]的隐式实例，并调用了包含的函数 fn。

然后，真正的魔力:

implicit def recFlattenFn[T, U](
  implicit f: Flat[T, U] = Flat((xs: T) => List(xs))
) = Flat((xs: List[T]) => xs flatMap f.fn)

这满足了 recFlatten所需的隐式参数，并且还采用了另一个隐式参数。最关键的是:

recFlattenFn可以充当其自己的隐式参数

它返回一个Flat [List [X]，X]，因此，如果recFlattenFn是Flat[T,U]

，则 T仅隐式地解析为 List。

如果隐式解析失败(即f不是T)，则隐式List可以回退到默认值

也许在以下示例之一的上下文中可以最好地理解这一点:

recFlatten(List(List(1, 2, 3), List(4, 5))) 

类型T推断为List[List[Int]]

尝试对`Flat [List [List [List [Int]]，U]

进行隐式查找

这与递归定义的recFlattenFn

相匹配

广义地说:

recFlattenFn[List[List[Int]], U] ( f =
  recFlattenFn[List[Int], U] ( f =
    Flat[Int,U]((xs: T) => List(xs)) //default value
  )
)

请注意， recFlattenFn仅与隐式搜索 Flat[List[X], X]匹配，并且params [Int,_]类型未能通过此匹配，因为 Int不是 List。这就是触发回退到默认值的原因。

类型推论也向后插入该结构，在每个递归级别上解决 U参数:

recFlattenFn[List[List[Int]], Int] ( f =
  recFlattenFn[List[Int], Int] ( f =
    Flat[Int,Int]((xs: T) => List(xs)) //default value
  )
)

这只是 Flat实例的嵌套，每个实例(最里面的实例除外)都执行 flatMap操作，以展开嵌套的 List结构的一级。最里面的 Flat只是将所有单个元素都包装在一个 List中。

Q.E.D.