48

Haskell では、他の多くの関数型言語と同様に、関数foldlは次のように定義されfoldl (-) 0 [1,2,3,4] = -10ます。

foldl (-) 0 [1, 2,3,4]は、定義により、 であるため、これで問題ありません((((0 - 1) - 2) - 3) - 4)。

しかし、Racket では2 です。これ(foldl - 0 '(1 2 3 4))は、Racket が「インテリジェントに」次のように計算するためです: (4 - (3 - (2 - (1 - 0))))、実際には 2 です。

もちろん、次のように補助関数 Flip を定義すると:

(define (flip bin-fn)
  (lambda (x y)
    (bin-fn y x)))

次に、Racket で Haskell と同じ動作を実現できます。代わりに、次のように(foldl - 0 '(1 2 3 4))記述できます。(foldl (flip -) 0 '(1 2 3 4))

問題はfoldl、なぜラケットでは、他の言語とは異なる、奇妙な (非標準的で直感的でない) 方法で定義されているのでしょうか?

4

4 に答える 4

68

  • Haskell の定義は統一されていません。Racket では、両方のフォールドへの関数の入力順序が同じであるため、置き換えて同じ結果を得ることができfoldlますfoldr。Haskell バージョンでこれを行うと、(通常は) 異なる結果が得られます — これは、2 つの異なるタイプで確認できます。

    (実際、適切な比較を行うためには、両方の型変数が整数であるこれらのおもちゃの数値の例は避けるべきだと思います。)

  • これには、セマンティックの違いに応じてfoldlまたはのいずれかを選択することが奨励される、素晴らしい副産物があります。foldr私の推測では、Haskell の順序を使用すると、操作に応じて選択する可能性が高くなります。これの良い例があります: あなたはfoldl各数値を減算したいので使用しました — これは非常に「明白な」選択であるためfoldl、怠惰な言語では通常悪い選択であるという事実を見落としがちです。

  • もう 1 つの違いは、通常の方法で Haskell バージョンが Racket バージョンよりも制限されていることです。Racket は任意の数のリストを受け入れることができるのに対し、Haskell バージョンは厳密に 1 つの入力リストで動作します。これにより、入力関数の引数の順序を統一することがより重要になります)。

  • 最後に、Racket が「他の多くの関数型言語」から分岐したと仮定するのは誤りです。折り畳みは決して新しいトリックではなく、Racket は Haskell (またはこれらの他の言語) よりもはるかに古いルーツを持っているからです。したがって、質問は逆になる可能性があります。なぜ Haskellfoldlは奇妙な方法で定義されているのでしょうか? （いいえ、(-)良い言い訳ではありません。）

過去の更新:

これは何度も何度も人々を悩ませているように見えるので、私は少し足を踏み入れました. これは決して決定的なものではなく、私の勝手な推測にすぎません。詳細を知っている場合は、これを自由に編集してください。または、関係者にメールして質問することをお勧めします。具体的には、これらの決定が行われた日付がわからないため、次のリストは大まかな順序です.

  • 最初に Lisp があり、あらゆる種類の「フォールド」については言及されていませんでした。reduce代わりに、特にその型を考慮すると、Lisp には非常に不均一なものがあります。たとえば:from-end、左スキャンか右スキャンかを決定するキーワード引数であり、異なるアキュムレータ関数を使用します。これは、アキュムレータ タイプがそのキーワードに依存することを意味します。これは他のハックに追加されます: 通常、最初の値はリストから取得されます ( を指定しない限り:initial-value)。最後に、 を指定せず:initial-value、リストが空の場合、実際にはゼロ引数に関数を適用して結果を取得します。

    これはすべて、reduce通常、その名前が示すように使用されることを意味します。つまり、値のリストを単一の値に減らします。通常、2 つの型は同じです。ここでの結論は、折りたたみと似たような目的を果たしているということですが、折りたたみで得られる一般的なリスト反復構造ほど有用ではありません。reduceこれは、 とその後の折り畳み操作の間に強い関係がないことを意味していると推測しています。

  • Lisp に従い、適切な折り畳みを持つ最初の関連言語は ML です。以下のnewacctの回答に記載されているように、そこで行われた選択は、均一なタイプのバージョン（つまり、Racketが使用するもの）を使用することでした。

  • 次のリファレンスは、Bird & Wadler の ItFP (1988) で、さまざまな型(Haskell など) を使用しています。ただし、彼らは付録で、ミランダが同じタイプ（ラケットの場合と同様）であることに注意しています。

  • Miranda は後で引数の順序を変更しました(つまり、Racket の順序から Haskell の順序に移動しました)。具体的には、そのテキストは次のように述べています。

    警告 - この foldl の定義は、古いバージョンの Miranda のものとは異なります。ここにあるものは、Bird and Wadler (1988) のものと同じです。古い定義では、「op」の 2 つの引数が逆になっていました。

  • Haskell は、さまざまなタイプを含め、ミランダから多くのものを取得しました。(しかし、もちろん日付がわからないので、Miranda の変更は Haskell によるものだったのかもしれません。) いずれにせよ、この時点でコンセンサスがなかったことは明らかです。したがって、上記の逆の質問が成り立ちます。

  • OCaml は Haskell 方向に進み、さまざまな型を使用する

  • 「How to Design Programs」(別名 HtDP) はほぼ同じ時期に書かれ、同じタイプを選択したと推測しています。ただし、動機や説明はありません。実際、その演習の後、組み込み関数の 1 つとして単に言及されています。

    もちろん、折り畳み操作のラケットの実装は、ここで言及されている「組み込み」でした。

  • その後、 SRFI-1が登場し、同じタイプのバージョン (Racket と同じ) を使用することが選択されました。この決定は、ジョン・デビッド・ストーンによる質問であり、彼は SRFI のコメントを指摘し、次のように述べています。

    注: MIT スキームと Haskell は、関数reduceとfold関数の F の引数の順序を反転します。

    オリンは後にこれに対処しました：彼が言ったのは次のことだけでした：

    良い点ですが、2 つの関数の一貫性が必要です。最初の状態値: srfi-1、SML 状態値の最後: Haskell

    特に彼のstate-valueの使用に注意してください。これは、一貫した型が演算子の順序よりもおそらく重要なポイントであるという見解を示唆しています。

于 2012-01-08T20:14:11.287 に答える
9

「他のどの言語とも違う」

反例として、標準 ML (ML は非常に古く、影響力のある関数型言語です)foldlも次のように機能します: http://www.standardml.org/Basis/list.html#SIG:LIST.foldl:VAL

于 2012-01-09T03:38:06.097 に答える
8

Racket のfoldlとfoldr(およびSRFI-1 の foldとfold-right) には、次のプロパティがあります。

(foldr cons null lst) = lst
(foldl cons null lst) = (reverse lst)

その理由で引数の順序が選択されたと推測します。

于 2012-01-08T18:08:38.757 に答える
3

ラケットのドキュメントから、次の説明foldl:

(foldl proc init lst ...+) → any/c

ご質問の興味深い点は次の 2 つです。

入力リストは左から右にトラバースされます

と

foldl は定数空間で lst を処理します

簡単にするために単一のリストを使用して、その実装がどのように見えるかを推測します。

(define (my-foldl proc init lst)
  (define (iter lst acc)
    (if (null? lst)
        acc
        (iter (cdr lst) (proc (car lst) acc))))
  (iter lst init))

ご覧のとおり、左から右へのトラバーサルと定数スペースの要件は満たされていますが ( の末尾再帰に注意してくださいiter)、の引数の順序procは説明で指定されていません。したがって、上記のコードを呼び出した結果は次のようになります。

(my-foldl - 0 '(1 2 3 4))
> 2

このように引数の順序を指定した場合proc:

(proc acc (car lst))

結果は次のようになります。

(my-foldl - 0 '(1 2 3 4))
> -10

私の要点は、 のドキュメントはfoldlの引数の評価順序について何の仮定もしていないということprocです。一定のスペースが使用され、リスト内の要素が左から右に評価されることを保証する必要があるだけです。

補足として、次のように記述するだけで、式の目的の評価順序を取得できます。

(- 0 1 2 3 4)
> -10
于 2012-01-08T16:18:19.993 に答える