这种递归List flattening如何工作？

Question

前一阵子在Scala邮件列表上被询问并回答:

凯文:

给定一些嵌套结构:List[List[...List[T]]] 将它展平为最佳(最好是类型安全)的方法是什么List[T]

加斯帕:

隐含和默认参数的组合起作用:

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这里也可以是a List[U],或a U或a List[List[List[U]]]等.通常,这样的函数可以直接指定为参数的类型.但是我们将在implicits中使用这个,因此命名的包装器可以避免任何隐式冲突的风险.

然后,从recFlatten以下方向向后工作:

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

此方法将采用xs(a List[T])并将其转换为a 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]if T是aList
• f如果隐式解析失败,则隐式可以回退到默认值(即T不是a List)

也许在其中一个例子的背景下最好地理解这一点:

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

• 该类型T被推断为List[List[Int]]
• 尝试对Flat [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只会匹配a的隐式搜索,Flat[List[X], X]并且类型params [Int,_]会失败,因为Int它不是a 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.

QED