OCamlでの木の折り畳み方法

1. 木の型定義: まず、折り畳みを行うために、木の型を定義します。以下は単純な二分木の例です。

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

2. 木の折り畳みの基本形: 折り畳み操作は、木の各ノードに対して畳み込み関数を適用し、木全体を単一の値にまとめるものです。以下は、基本形のコード例です。

let rec fold_tree f acc tree =
  match tree with
  | Leaf -> acc
  | Node (value, left, right) ->
    let acc' = fold_tree f acc left in
    let acc'' = f acc' value in
    fold_tree f acc'' right

このコードでは、畳み込み関数 f を定義し、acc を初期値として折り畳む関数 fold_tree を再帰的に呼び出しています。各ノードで畳み込み関数が適用され、最終的な結果が返されます。

3. 木の要素の合計を求める例: 以下の例では、畳み込み関数として木の要素を合計する関数を定義します。

let sum_elements acc value = acc + value
let tree = Node (1, Node (2, Leaf, Leaf), Node (3, Leaf, Leaf))
let result = fold_tree sum_elements 0 tree

この例では、木の全ての要素の合計を求めるために、畳み込み関数 sum_elements を定義し、初期値として 0 を指定しています。最終的な結果は result に格納されます。