4

更新-解決策

彼の助けをくれたjacobmのおかげで、私は解決策を思いついた。

// Folding Recursion
let reverse_list_3 theList = 
    List.fold_left (fun element recursive_call -> recursive_call::element) [] theList;;

私はOCaml（クラス用）での再帰のさまざまな方法について学び、いくつかの演習では、さまざまな再帰スタイルを使用してリストを逆にする関数を書いています。

// Forward Recursion
let rec reverse_list_forward theList =
    match theList with [] -> [] | (head::tail) -> (reverse_list_1 tail) @ [head];;

// Tail Recursion
let rec reverse_list_tail theList result =
    match theList with [] -> result | (head::tail) -> reverse_list_2 tail (head::result);;

今、私はを使って逆関数を書き込もうとしていますList.fold_leftが、行き詰まっていて理解できません。折りたたみを使用してこの逆関数をどのように記述しますか？

また、関数型プログラミング、さまざまなタイプの再帰、高階関数などについての参考資料があれば、リンクをいただければ幸いです:)

4

2 に答える 2

8

折り畳み操作を、一連の操作で何をすべきかの一般化と考えると役立つと思います。

a + b + c + d + e

fold_right (+) 0基本ケースとして+使用して、操作を右結合的に適用します。0

(a + (b + (c + (d + (e + 0)))))

fold_left 0 (+)左結合的に適用します。

(((((0 + a) + b) + c) + d) + e)

ここで、右折と左折の両方+で with::と0withを置き換えるとどうなるかを考えてみましょう。[]

リストのand演算子を「置き換える」ように、方法fold_leftと作業を考えることも役立つ場合があります。たとえば、リストは実際には. たとえば、 とで「置換」できると考えると便利な場合があります。fold_right::[][1,2,3,4,5]1::(2::(3::(4::(5::[]))))fold_right op base::op[]base

fold_right (+) 0 1::(2::(3::(4::(5::[]))))

になる

1 + (2 + (3 + (4 + (5 + 0))))

::+になり[]まし0た。この観点からするとfold_right (::) []、元のリストが返されるだけであることが簡単にわかります。fold_left base opリストの周りのすべての括弧を逆方向に書き換え、リスト[]の後ろから前に移動し、次にandに置き換えます。たとえば、次のようになります。::op[]base

fold_left 0 (+) 1::(2::(3::(4::(5::[]))))

になる

(((((0 + 1) + 2) + 3) + 4) + 5)

+と0を使用するfold_leftとfold_right、同じ結果が得られます。しかし、それ以外の場合はそうではありません: たとえば、代わりに+使用した場合-、結果は異なります: 1 - (2 - (3 - (4 - (5 - 0)))) = 3, but ((((( 0 - 1) - 2) - 3) - 4) - 5) = -15。

于 2011-09-12T00:11:35.083 に答える
0 
let rev =
  List.fold_left ( fun lrev b ->
    b::lrev
  ) [];;

テスト：

# rev [1;2;3;4];;
- : int list = [4; 3; 2; 1]
于 2015-10-05T21:11:45.677 に答える