37

Scala で関数型プログラミングを行っているときに、次の質問に出くわしました。

foldRight に関して、foldLeft を正しく使用できますか? 逆にどうですか？

著者が提供するソリューションでは、次のような実装を提供しています。

def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B = 
    foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)

  def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = 
    foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

誰かがこのソリューションをたどって、これが実際にfoldrの観点からfoldlをどのように実装するか、またはその逆を理解するのを手伝ってくれますか?

ありがとう

4

4 に答える 4

33

見てみましょう

def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B = 
  foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

（他の折り方も同様です）。トリックは、正しい折り畳み操作中に、 type の最終的な値を構築しないことですB。代わりに、 to から関数を作成しBますB。折りたたみステップは、型の値a: Aと関数を取りg: B => B、新しい関数を生成します(b => g(f(b,a))): B => B。gこの関数はwithの合成として表現できますf(_, a):

  l.foldRight(identity _)((a,g) => g compose (b => f(b,a)))(z);

プロセスは次のように見ることができます: の各要素に対してa、関数であるl部分適用を取ります。次に、これらすべての関数を、一番右の要素 (トラバーサルを開始する要素) に対応する関数が構成チェーンの左端になるように構成します。最後に、大きな合成関数を に適用します。これにより、左端の要素 (合成チェーンの右端にある要素) から始まり、右端の要素で終了する一連の操作が行われます。b => f(b,a)B => Bz

更新:例として、この定義が 2 つの要素のリストでどのように機能するかを調べてみましょう。まず、関数を次のように書き直します。

def foldLeftViaFoldRight[A,B](l: List[A], z: B)
                             (f: (B,A) => B): B =
{
  def h(a: A, g: B => B): (B => B) =
    g compose ((x: B) => f(x,a));
  l.foldRight(identity[B] _)(h _)(z);
}

それを渡すとどうなるか計算してみましょうList(1,2):

List(1,2).foldRight(identity[B] _)(h _)
  = // by the definition of the right fold
h(1, h(2, identity([B])))
  = // expand the inner `h`
h(1, identity[B] compose ((x: B) => f(x, 2)))
  =
h(1, ((x: B) => f(x, 2)))
  = // expand the other `h`
((x: B) => f(x, 2)) compose ((x: B) => f(x, 1))
  = // by the definition of function composition
(y: B) => f(f(y, 1), 2)

この関数をz利回りに適用する

f(f(z, 1), 2)

要求に応じ。

于 2013-06-16T19:46:42.217 に答える
14

私はこの演習を行ったばかりで、誰かに役立つことを期待して、どのように答えにたどり着いたかを共有したいと思います (基本的には質問の内容と同じで、文字だけが異なります)。

背景として、何を何をするかから始めましょfoldLeftうfoldRight。たとえば、リスト [1, 2, 3] に対する foldLeft の結果は、操作*と開始値zが値です。 ((z * 1) * 2) * 3

foldLeft は、リストの値を左から右に段階的に消費するものと考えることができます。言い換えると、最初に値z(リストが空の場合の結果) から開始し、リストfoldLeftが 1 で始まりz * 1、値が、そして最後に 3 を作用させた後、値 になります。foldLeft2(z * 1) * 2((z * 1) * 2) * 3

                             1    2    3
Initially:               z
After consuming 1:      (z * 1)
After consuming 2:     ((z * 1) * 2
After consuming 3:    (((z * 1) * 2) * 3

この最終的な値は、（演習で求められるように）foldRight代わりに使用することを除いて、達成したい値です。foldLeftここで、リストの値を左から右に消費するのと同様に、リストの値を右から左に消費することに注意してくださいfoldRight。したがって、リスト [1, 2, 3] では、

  • この foldRight は 3 と [何か] に作用し、[結果] を返します
  • 次に、2 と [result] に作用し、[result2] を与えます。
  • 最後に、それは 1 と [result2] に作用し、最終的な式を与えます
  • 最終的な表現を(((z * 1) * 2) * 3

言い換えるfoldRightと、 を使用すると、最初にリストが空の場合の結果、次にリストに [3] しか含まれていない場合の結果、次にリストが [2, 3] の場合の結果、そして最後に結果に到達します。リストは [1, 2, 3] です。

つまり、これらは を使用して到達したい値ですfoldRight:

                             1    2    3
Initially:                             z
After consuming 3:                 z * 3
After consuming 2:           (z * 2) * 3
After consuming 1:     ((z * 1) * 2) * 3

したがって、 からzまで(z * 3)に移動(z * 2) * 3する必要があり((z * 1) * 2) * 3ます。

値として、これを行うことはできません。任意の操作に対して、値(z * 3)から値に移動する自然な方法はありません。(交換可能で結合的であるため、乗算用がありますが、任意の操作を表すためにのみ使用しています。)(z * 2) * 3**

しかし、関数としてこれを行うことができるかもしれません! 「プレースホルダー」または「穴」を備えた関数が必要ですz。これは、それを適切な場所に配置するものです。

  • たとえば、最初のステップの後 (3 に作用した後) には、プレースホルダー関数がありますz => (z * 3)。というか、関数は任意の値を取る必要がありz、特定の値に使用してきたので、これを と書きましょうt => (t * 3)。(この関数を入力に適用するとz、値が得られます(z * 3)。)
  • 2 番目のステップの後 (2 と結果に作用した後)、おそらくプレースホルダー関数がありt => (t * 2) * 3ますか?

最初のプレースホルダー関数から次のプレースホルダー関数に移動できますか? させて

      f1(t) = t * 3
and   f2(t) = (t * 2) * 3

f2に関しては何f1ですか？

f2(t) = f1(t * 2)

はい、できます！したがって、必要な関数は と を取り2、f1を与えf2ます。これを と呼びましょうg。私たちはg(2, f1) = f2どこにいるf2(t) = f1(t * 2)のか、言い換えれば

g(2, f1) = 
    t => f1(t * 2)

先に進めた場合にこれが機能するかどうか見てみましょう: 次のステップはRHS がorg(1, f2) = (t => f2(t * 1))と同じです。t => f1((t * 1) * 2))t => (((t * 1) * 2) * 3)

うまくいくようです！最後にz、この結果に適用します。

最初のステップは何ですか？上記で定義されているように、またの定義からも におよびを適用gします。したがって、アイデンティティ関数である必要があるようです。3f0f1f1(t) = t * 3f1(t) = f0(t * 3)gf0

新たに始めましょう。

Our foldLeft(List(1, 2, 3), z)(*) is ((z * 1) * 2) * 3
Types here: List(1, 2, 3) is type List[A]
             z is of type B
             * is of type (B, A) -> B
             Result is of type B
We want to express that in terms of foldRight
As above:
 f0 = identity. f0(t) = t.
 f1 = g(3, f0). So f1(t) = f0(t * 3) = t * 3
 f2 = g(2, f1). So f2(t) = f1(t * 2) = (t * 2) * 3
 f3 = g(1, f2). So f3(t) = f2(t * 1) = ((t * 1) * 2) * 3

最後に、z に f3 を適用して、必要な式を取得します。すべてがうまくいきます。そう

f3 = g(1, g(2, g(3, f0)))

つまり、f3 =foldRight(xs, f0)(g)

g今回はx * y、任意の関数を使用する代わりに、 を定義しましょうs(x, y)。

  • への最初の引数gはタイプですA
  • 2 番目の引数 togは、これらfの型であり、これはB => B
  • だからタイプgは(A, (B=>B)) => (B=>B)

  • そうgです：

    def g(a: A, f: B=>B): B=>B = 
    (t: B) => f(s(t, a))

これらすべてをまとめる

def foldLeft[A, B](xs: List[A], z: B)(s: (B, A) => B): B = {
    val f0 = (b: B) => b

    def g(a: A, f: B=>B): B=>B =
        t => f(s(t, a))

    foldRight(xs, f0)(g)(z)
}

この本を読んでいるこのレベルでは、より明確で理解しやすいので、私は実際にはこの形式を好みます。しかし、ソリューションの形式に近づくために、f0andの定義をインライン化できます (これが入力であり、コンパイラーがそれを推論するためg、 の型を宣言する必要はもうありません)。gfoldRight

def foldLeft[A, B](xs: List[A], z: B)(s: (B, A) => B): B =
  foldRight(xs, (b: B) => b)((a, f) => t => f(s(t, a)))(z)

これはまさに問題の内容であり、記号が異なるだけです。foldRight についても、foldLeft に関して同様です。

于 2016-08-10T18:50:40.447 に答える
7

そのコードは、リスト内の要素ごとに 1 つの関数で、複数の関数オブジェクトを連鎖させています。これをより明確に示す例を次に示します。

val f = (a: Int, b: Int) => a+b
val list = List(2,3,4)
println(list.foldLeft(1)(f))

val f1 = (b: Int) => f(b, 2)
val f2 = (b: Int) => f(b, 3)
val f3 = (b: Int) => f(b, 4)
val f4 = (b: Int) => b

val ftotal = f1 andThen f2 andThen f3 andThen f4
println(ftotal(1))

関数オブジェクトのリンクされたリストとして想像できます。値を渡すと、すべての関数を「流れ」ます。これは、データフロー プログラミングに少し似ています。

于 2013-06-16T22:54:06.963 に答える