この再帰的なリストの平坦化はどのように機能しますか？

Question

Aバックthis was asked and answered Scalaのメーリングリストの中：

ケビン：

考えると、いくつかの入れ子構造：List[T]

にそれを平らにするための最良の（好ましくはタイプセーフ）の方法は何 List[List[...List[T]]]

ジェスパー：

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 

この方法は、（List[T]を）xsを取り、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を取ります。最も決定的：Flat[T,U]場合TがList あるよう

• recFlattenFnは、独自の暗黙のパラメータとして機能することができ、それがフラット返し
• [一覧[X]は、X]、そうrecFlattenFnは、暗黙的に解決されます
• 暗黙的な解決が失敗した場合、暗黙的なfはデフォルト値にフォールバックすることができます（つまりTがListではありません）

Perha PSこれは最高の例の一つの文脈で理解されています

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

• List[List[Int]]
• 暗黙のルックアップが `フラット[一覧[一覧[INT]]のために試みられているようなタイプTが、推測されU]
• これは再帰的にrecFlattenFn

は概して定義にマッチさ：

が Listではないので [Int,_]は、この試合を失敗のparams recFlattenFnだけ Flat[List[X], X]の暗黙的な検索やタイプと一致することをは

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

注意。これがデフォルト値へのフォールバックをトリガするものです。

タイプ推論はまた、再帰の各レベルでU PARAMを解決する、その構造まで逆方向に動作：

Flatインスタンスだけネスティング、 flatMapを行う（最内を除く）各一つ

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

入れ子になったList構造の1つのレベルを展開する操作。最も内側のFlatは、すべての個々の要素を1つのListにバックアップします。

Q.E.D.

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の種類は、あなたがまだU3の種類を推測することはできませんIntですが、あなたは、あなたがいることをFlat[List[Int, U3]]オブジェクトが必要になりますことを知っています暗黙的に提供される。 「暗黙の候補」は1つだけです。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の解像度であなたを残します。