此递归列表展平如何工作? [英] How does this recursive List flattening work?

问题描述

前一阵子这是问到的并在Scala邮件列表中回答了:

凯文:

给出一些嵌套结构:List[List[...List[T]]] 将其展平为List[T]

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

Jesper:

隐式参数和默认参数的组合有效:

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) 

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

I have been looking at this code for a while. I cannot figure out how it works. There seems to be some recursion involved... Can anybody shed some light? Are there other examples of this pattern and does it have a name?

推荐答案

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

Oh wow, this is an old one! I'll start by cleaning up the code a bit and pulling it into line with current idiomatic conventions:

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类:

Then, without further ado, break down the code. First, we have our Flat class:

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

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

This is nothing more than a named wrapper for the function T => List[U], a function that will build a List[U] when given an instance of type T. Note that T here could also be a List[U], or a U, or a List[List[List[U]]], etc. Normally, such a function could be directly specified as the type of a parameter. But we're going to be using this one in implicits, so the named wrapper avoids any risk of an implicit conflict.

然后，从recFlatten向后工作:

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

此方法将采用xs(a List[T])并将其转换为U.为此，它找到Flat[T,U]的隐式实例并调用附带的函数fn

This method will take xs (a List[T]) and convert it to a U. To achieve this, it locates an implicit instance of Flat[T,U] and invokes the enclosed function, 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所需的隐式参数，它还采用了另一个隐式参数.最关键的是:

This satisfies the implicit parameter required by recFlatten, it also takes another implicit paramater. Most crucially:

• recFlattenFn可以充当其自己的隐式参数
• 它返回Flat [List [X]，X]，因此，如果T是List
，则recFlattenFn仅将隐式解析为Flat[T,U]. 如果隐式解析失败(即T不是List)，则
• 隐式f可以回退到默认值

• recFlattenFn can act as its own implicit parameter
• it returns a Flat[List[X], X], so recFlattenFn will only be implicitly resolved as a Flat[T,U] if T is a List
• the implicit f can fallback to a default value if implicit resolution fails (i.e. T is NOT a List)

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

Perhaps this is best understood in the context of one of the examples:

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

• 类型T推断为List[List[Int]]
• 尝试对"Flat [List [List [List [Int]]，U]"进行隐式查找
• 这与递归定义的recFlattenFn
相匹配
• The type T is inferred as List[List[Int]]
• implicit lookup is attempted for a `Flat[List[List[Int]], U]
• this is matched by a recursively defined 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不是List，因此类型params [Int,_]未能通过此匹配.这就是触发回退到默认值的原因.

Note that recFlattenFn will only match an implicit search for a Flat[List[X], X] and the type params [Int,_] fail this match because Int is not a List. This is what triggers the fallback to the default value.

类型推断也可以在该结构上向后推，在每个递归级别上解析U参数:

Type inference also works backwards up that structure, resolving the U param at each level of recursion:

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中.

Which is just a nesting of Flat instances, each one (except the innermost) performing a flatMap operation to unroll one level of the nested List structure. The innermost Flat simply wraps all the individual elements back up in a single List.

Q.E.D.

这篇关于此递归列表展平如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！