scala – 这个递归列表如何平坦化？

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 =>的命名包装器列表[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] = Flat((xs: T) => List(xs))
) = Flat((xs: List[T]) => xs flatMap f.fn)

这满足recFlatten所需的隐式参数,它也需要另一个隐式参数.最关键的是

> recFlattenFn可以作为自己的隐式参数
>它返回一个Flat [List [X],X],所以recFlattenFn只会被隐式解析为Flat [T,U],如果T是一个列表
>如果隐式解析失败(即T不是列表),隐式f可以回退到默认值

也许这在一个例子的上下文中是最好的理解的：

recFlatten(List(List(1,5)))

>类型T推断为List [List [Int]]
对于’Flat [List [List [Int]],尝试进行隐式查找
>这被一个递归定义的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]和类型参数[Int,_]在此匹配中失败的隐含搜索,因为Int不是列表.这是什么触发回退到默认值.

类型推断也可以向上运行该结构,在每个递归级别解析U参数：

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

这只是一个平面实例的嵌套,每个(最内层除外)执行一个flatMap操作来展开嵌套列表结构的一个层次.最内层的Flat简单地将所有的单个元素包装在单个列表中.

证明完毕