fold_left/rightを使用してOCAMLのリストを逆にします

Question

更新 - 解決策

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 しかし、私は立ち往生していて、それを理解することはできません。折りたたみを使用してこの逆関数をどのように記述しますか？

また、機能的なプログラミング、さまざまな種類の再帰、高次の双方向などについて良い参照がある場合、リンクは大歓迎です:)

Answer 1

折り畳み操作を一連の操作をどうするかの一般化と考えるのは役に立ちます

a + b + c + d + e

fold_right (+) 0 を適用します + 右分類の操作、使用 0 基本ケースとして：

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

fold_left 0 (+) それを左結合して適用します：

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

次に、交換した場合に何が起こるかを考えてください + と :: と 0 と [] 右倍と左倍の両方で。

---

方法について考えることも役に立つかもしれません 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 少し奇妙なことをしてください：リストの周りのすべての括弧を書き直して、他の方向に進み、動きます [] リストの背面から正面まで、そして それから 交換 :: と 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、が（（（（0-1） - 2） - 3） - 4） - 5） = -15。

Answer 2

let rev =
  List.fold_left ( fun lrev b ->
    b::lrev
  ) [];;

テスト：

# rev [1;2;3;4];;
- : int list = [4; 3; 2; 1]