0

永続的な配列を使用してユニオン検索アルゴリズムを作成しています。ここに私が使用できるいくつかの機能があります：

Array.sub : 'a array * int -> 'a
Array.update: 'a array * int * 'a -> unit

テーブルを作成する必要があります

 datatype 'a table = Array of 'a Array.array | Change of int * 'a * 'a table ref

Change コンストラクターとライブラリーを使用して、一定時間内に 1 スロットだけ異なる既存のものから

Array.tabulate : int * (int-> 'a)-> 'a array

各要素が独自のパーティションであるサイズ n のテーブルへの参照を返す関数を実装します。

newTable : int -> int table ref

これが私の試みですが、私は本当に混乱しているので、助けていただければ幸いです:

fun newTable n = 
        if 0 = Array.sub(Array.tabulate (n,fn i => i), 0) 
            then () 
        else 
           ref(Change(Array.array(n)));
4

1 に答える 1

0

あなたの問題を正しく理解しているかどうかはわかりませんが、あなたの問題があなたにしてほしいと思うことから答えようとします.

newTable署名を見ると、入力intを受け取り、 を返すことがわかりますint table ref。ソリューションは を返すunitため、型チェックは行われません。

の目標はnewTable、互いに異なる整数のテーブルの参照を返すことです。を使用して異なる (増加する) 整数の配列を作成できることは既に理解していますArray.tabulate。ただし、tableではなく、を再実行する必要がありますarray。データ型の定義は、tableを使用してそれを生成する方法を示しているため、生成arrayした配列を次のようにラップするだけです。

fun newTable n = 
    ref (Array (Array.tabulate (n,fn i => i)))

このnewTable関数は、 Union Find WP articleで説明されているMakeSet操作と同等であり、シングルトンではなくセット全体を生成するように改善されています。

于 2013-03-29T13:25:55.527 に答える