1

データ型が与えられた場合:

datatype bunch = One of int
               | Group of bunch list;
datatype 'ex bunch = NIL
                   | One of 'ex
                   | Group of 'ex * 'ex bunch;

たとえば、この再帰関数の合計を返す関数を設計するにはどうすればよいですか。再帰関数を定義する方法とその使用方法を少し理解していますが、「ex」がオンラインでデータ型の束をどのように変更するか、または他の参考文献を見つけることができません。

4

1 に答える 1

0

2 番目の定義は、bunchデータ構造を多態性にします。つまり、任意の型のデータを含めることができます。たとえば、Group (3, One 2)はint bunchであり、Group ("three", One "two")はstring bunchです。値NILには、任意の型を表す型'a bunchがあり'aます (つまりNIL、型int bunchと型string bunchと ... があります)。

「この再帰関数の合計を返す」という目標は意味がありません。再帰関数がありません。「この帰納的なデータ構造の合計を返す」という意味であったとしても、何を求めているのかはまだ明確ではありません。数値の集合ではないデータ構造の合計が何を意味するのかについて、より正確にする必要があります。

次の関数は、 の整数の合計を計算しますint bunch。ML インタープリターに入力するとわかるように、その型は ですint bunch -> int。つまり、整数の束に対してのみ作用します (そうでなければ、+演算子は意味をなさないでしょう)。

fun bunch_sum NIL = 0
  | bunch_sum (One x) = x
  | bunch_sum (Group (x, b)) = x + bunch_sum b;

次の関数は、任意の要素タイプ (その type で示される'a bunch -> int) を持つ束の要素数を計算します。このような多態性関数を定義できる理由は、操作するために束の要素の内部を調べる必要がないためです。それはパラメトリックに多態性です。

fun bunch_count NIL = 0
  | bunch_count (One x) = 1
  | bunch_count (Group (x, b)) = 1 + bunch_count b;

(本番プログラムでは、このような関数は、末尾再帰アルゴリズムを使用して、明確ではないがリソースを消費しない方法で記述する必要があります。)

束の型はリストとほぼ同形であるため、実装の標準リスト ライブラリのソースを参照してインスピレーションを得ることができます。

于 2010-10-10T10:43:25.960 に答える