這個遞歸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。