3

私はデータ構造を持っています、

datatype 'a tree = Leaf | Branch of 'a tree * 'a * 'a tree

このツリーをある順序でトラバースする関数を書きたいと思います。それが何をするかは問題ではないので、treefold : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'b. この関数は次のように記述できます。

fun treefold f acc1 Leaf = acc1
  | treefold f acc1 (Branch (left, a, right)) =
    let val acc2 = treefold f acc1 left
        val acc3 = f (a, acc2)
        val acc4 = treefold f acc3 right
    in acc4 end

しかし、最後のケースでは必然的に 2 つの分岐があるため、これは末尾再帰関数ではありません。

型シグネチャの展開が許可されている場合、それを作成することは可能ですか?また、どのような費用がかかりますか? また、試してみる価値があるかどうかも疑問です。つまり、実際に速度が向上しますか?

4

2 に答える 2

5

継続渡しスタイルを使用して、末尾再帰的なツリーフォールドを実現できます。

fun treefold1 f Leaf acc k = k acc
  | treefold1 f (Branch (left, a, right)) acc k =
    treefold1 f left acc (fn x => treefold1 f right (f(a, x)) k)

fun treefold f t b = treefold1 f t b (fn x => x)

例えば：

fun sumtree t = treefold op+ t 0

val t1 = Branch (Branch(Leaf, 1, Leaf), 2, Branch (Leaf, 3, Leaf))

val n = sumtree t1

予想どおり n = 6 になります。

于 2013-09-29T13:45:28.253 に答える