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 构造函数和库，从一个在恒定时间内只不同一个槽的现有槽

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签名，您可以看到它接受一个inton 输入，并返回一个int table ref. 您的解决方案返回unit，因此不会进行类型检查。

的目标newTable是在彼此不同的整数表上返回一个引用。您已经了解可以使用Array.tabulate. 但是您必须重新运行 a table，而不是array. 数据类型的定义table告诉我们如何使用 生成它array，所以你所要做的就是像这样包装你生成的数组：

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

该newTable功能等效于Union Find WP 文章中描述的MakeSet操作，经过改进以生成整个集合而不是单例。

于 2013-03-29T13:25:55.527 回答