这个递归List扁平化工作如何？

Question

A中，而斯卡拉邮件列表上回this was asked and answered：

凯文：

鉴于一些嵌套结构：List[List[...List[T]]] 什么是最好的（最好是类型安全的）的方式把它展平到List[T]

的Jesper：

IMPL的组合icits和缺省参数的工作原理：

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]一个名为包装器，给出T类型的实例时，将建立一个List[U]的功能。请注意，这里的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所需的隐含参数，它也需要另一个隐含paramater 。最关键的是：

• recFlattenFn可以作为自己的隐含参数行事
• 它返回一个扁平[列表[X]，X]，所以recFlattenFn只会被隐式解析为Flat[T,U]如果T是List
• 若隐解析失败的隐含f可以回退到默认值（即T不是一个List）

Perha PS，这是最好的在实施例之一的上下文中理解：

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

• 类型T被推断为List[List[Int]]
• 隐查找尝试用于`平[列表[列表[INT]] C]
• 这是通过一个匹配递归定义recFlattenFn

广义地说：

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

注意PARAMS [Int,_]失败，这场比赛，因为Int不是ListrecFlattenFn将只匹配了Flat[List[X], X]和隐式的搜索类型。这是触发回退到默认值的原因。

类型推断也倒过来了该结构，在递归的每个层次解决U PARAM：

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备份。

证明完毕

Answer 2

可能是一个很好的解决方案，就是试着看看这些类型是如何被传递的。为了避免混淆，让我们重命名泛型：

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

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

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

在第一种情况下，res0的T3类型是Int你不能推断出U3尚未类型，但你知道你需要一个Flat[List[Int, U3]]对象将隐含提供。只有一个“隐性候选人”：recFlattenFn函数的结果，其类型为Flat[List[T2], List[U2]]。因此T2 = Int和U2 = U3（我们仍然需要推断）。

现在，如果我们能够使用recFlatten，我们必须为其提供一个参数f。 这是诀窍。您可以使用类型为Flat[Int, U2]的隐式或类型Int => List[Int]的默认值。让我们看看可用的含义。如前所述recFlattenFn可以提供Flat[List[T2], U2]（用于新的T2和U2）对象。它不符合f的预期签名。因此，在这里没有隐含的合适的候选者，我们必须使用默认参数。由于默认参数的类型是Int => List [Int]，所以U2和U3是Int，我们去了。

希望这篇漫长的散文能帮助。我给你留下的分辨率为res1和res2。