8

ご存知かもしれませんが、OCamlにはfold_left、fold_right、filterなどの高階関数があります。

関数型プログラミングの私のコースでは、fold_treeという名前の関数が導入されました。これは、リストではなく（バイナリ）ツリーにあるfold_left/rightのようなものです。次のようになります。

 let rec fold_tree f a t = 
  match t with
    Leaf -> a |
    Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;

ツリーは次のように定義されます。

type 'a tree = 
  Node of 'a tree * 'a * 'a tree | 
  Leaf;;

OK、これが私の質問です：fold_tree関数はどのように機能しますか？いくつか例を挙げて、人間の言葉で説明してもらえますか？

4

5 に答える 5

8

これがスタイルの提案です。行の先頭にバーを配置します。ケースがどこから始まるかが明確になります。一貫性を保つために、最初のバーはオプションですが、推奨されます。

type 'a tree = 
  | Node of 'a tree * 'a * 'a tree
  | Leaf;;

let rec fold_tree f a t = 
    match t with
      | Leaf -> a
      | Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);;

それがどのように機能するかについては、次のツリーを検討してください。

let t = Node(Leaf, 5, Node(Leaf, 2, Leaf));;

タイプ付きint tree。

視覚的には、t次のようになります。

   5
  / \
 （）2
    / \
   （）（）

そして、fold_treeを呼び出すには、値を組み合わせる関数が必要です。Nodeケースでの使用法に基づいて、f3つの引数を取り、すべて同じタイプのツリーを取り、同じものを返します。これを行います：

let f x l r = x + l + r;; (* add all together *)
fold_tree f 1 t;;

それぞれの場合に何が起こるかを理解するのに役立ちます。いずれの場合もLeaf、aが返されます。いずれNodeの場合も、格納されている値と、左右のサブツリーを折りたたんだ結果を組み合わせます。この場合、各リーフが1つとしてカウントされる数を追加しているだけです。この木の折り畳みの結果はです10。

于 2010-11-15T23:10:25.017 に答える
5

ツリーの例を見てみましょう。

let t = Node (Node (Leaf, 10, Leaf), 1, Node (Node (Leaf, 20, Leaf), 11, Leaf))

fold操作の一般的な定義は、ツリー内のあらゆる場所でコンストラクターを関数に置き換えることです。

general_fold_tree node leaf t =
    node (node leaf 10 leaf) 1 (node (node leaf 20 leaf) 11 leaf)

nodeは、左のサブツリー、ノードコンテンツ、および右のサブツリーからツリーを構築するコンストラクターと同じように、左の何か、要素、および右の何かから何かを構築する関数です。は定数であり、定数コンストラクターと一致します。NodeleafLeaf

let rec general_fold_tree (node : 'b -> 'a -> 'b -> 'b) (leaf : 'a) (t : 'a tree) : 'b =
  let recurse t = general_fold_tree node leaf t in
  match t with
  | Node (l, x, r) -> node (recurse l) x (recurse r)
  | Leaf -> leaf

関数のタイプがタイプ定義のタイプと一致することに注意してください。ただし、タイプ定義がの構築を記述している'a tree場合、fold関数は任意のの構築を記述します'b。

一般的なフォールドによく似た操作は、フォールドと呼ばれます。たとえば、リストでList.fold_rightは、上記の定義による一般的なフォールドです。List.fold_leftは、関数を逆に適用するバリエーションです（より明確で効率的ですが、fold_leftreverse + + reverseと同等です）。fold_right

あなた自身fold_treeは、ノード関数がコンストラクターとは異なる順序で引数をとる、この一般的なフォールドの単純なバリエーションです。

let equrts_fold_tree f a t =
  let node l x r = f x l r in
  general_fold_tree node a t
于 2010-11-16T00:39:49.780 に答える
4

リストについて考える方法fold_rightは次のとおりです。たとえば、リストは

(1 :: (2 :: (3 :: [])))

そして、::（および[]の代わりに新しい定数）の代わりに新しい二項演算を使用してリストを再解釈します。

fold_right (+) l 0 = (1 + (2 + (3 + 0)))

リストにまったく何もしたくない場合は、関数を関数consとして渡し、空のリストをニュートラル要素として渡すことができます。したがって、ある意味でfold_rightは、非常に一般的です。情報をまったく失わないようにすることもできます。

あなたのfold_tree質問のは、木のデータ型についても同じ考えです。ツリーを再解釈する場合は、コンストラクターの代わりに適用されるノードの新しい関数をツリーに渡しますNode。同一のツリーを取得したい場合はLeaf、ニュートラルおよび(fun x l r -> Node (l, x, r))関数として適用できます。リストの場合と同様にfold_left、このサンプルアプリケーションはあまり興味深いものではありませんが、これはfold_left非常に一般的な変換であることを意味します（専門用語は射です）。

たとえば、関数を使用してツリーの要素を合計することもでき(fun x l r -> x + l + r)ます。

于 2010-11-15T23:12:03.890 に答える
3

あなたは読書を楽しむかもしれません

http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/

http://lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-three/

これはF＃にありますが、F＃はOCamlと非常によく似ています。

于 2010-11-16T02:01:32.240 に答える
3

これfは3つのパラメーターの削減関数でaあり、削減の中立要素でありt、ルートであるように思われるので、次のようになります。

次のようなバイナリが与えられます（バリアント型の構文をよく覚えていないので、ここで見下すようにしてください）

let r = Node(Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf)),1,Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf)))

すべてのノードを合計する場合、関数は次のように呼び出されます。

let add x y z = x + y + z
fold_tree add 0 r

tノードとして一致するので、次のようになります。

(add 1 (fold_tree add 0 Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf))) (fold_tree add 0 Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf))))

もう少し拡張すると、次のようになります。

(add 1 (add 2 (fold_tree add 0 Node(Leaf,3,Leaf)) (fold_tree add 0 Node(Leaf,4,Leaf))) (add 5 (fold_tree add 0 Node(Leaf,6,Leaf)) (fold_tree add 0 Node(Leaf,7,Leaf))))

そしてもう一度、葉を一致させます：

(add 1 (add 2 (add 3 0 0) (add 4 0 0)) (add 5 (add 6 0 0) (add 7 0 0))
(add 1 (add 2 3 4) (add 5 6 7))
(add 1 9 18)

最終的に取得するには：

28

それが役に立てば幸い。

于 2010-11-15T22:58:26.547 に答える