对于自动机算法,我需要一种功能语言的快速Union-Find数据结构.由于我需要正式证明数据结构的正确性,我宁愿选择一个简单的结构.
我想要做的是计算一组S关系中元素的等价类R ? S × S.我想最终得到的是一些函数f: S ? S,它将任何元素映射S到其R等价类的(规范)代表.通过"规范",我的意思是我不关心它是什么代表,只要它对于一个等价类的所有元素都是相同的,即我想要f x = f y ? (x,y) ? R持有.
在函数式语言中,最好的数据结构和算法是什么？我应该补充一点,我真的需要"正常"的功能代码,即没有可变性/状态变换器monad.
编辑:与此同时,我提出了这个算法:
m := empty map
for each s ? S do
if m s = None then
for each t in {t | (s,t) ? R}
m := m[t ? s]
这将创建一个映射,将任何元素映射S到其等价类的代表,其中代表是迭代所到达的第一个元素S.我认为这实际上有线性时间(如果地图操作是不变的).但是,我仍然对其他解决方案感兴趣,因为我不知道这在实践中有多高效.
(我的关系在内部表示为"S→(S Set)选项",因此迭代超过{t |(s,t)∈R} - 这是对该结构的廉价操作.)
algorithm functional-programming equivalence-classes data-structures union-find
我需要找到线性程序的精确实数解（其中所有输入都是整数）。重要的是，求解器还将解输出为有理数，理想情况下无需使用浮点数执行任何中间步骤。
GLPK 可以进行精确算术，但无法将解显示为有理数（即 1/3 得到 0.3333）。我可能可以尝试猜测这意味着哪个数字，但这似乎非常脆弱。
我无法找到可以做这种事情的 LP 求解器。有吗？性能并不是一个大问题；我的问题很小。（我确实考虑过使用像 Z3 这样的 SMT 求解器；它们可以解决此类问题并提供精确的有理解，但它们采用量词消除，而不是使用更适合线性规划（如 Simplex）的算法）
我想有一个功能
foo :: (a ? b ? c) ? [a] ? [b] ? [[c]]
采用一个函数f :: a ? b ? c和两个列表xs和ys并返回一个栅格(即,列表的列表)包含的值f应用于从值的每个组合xs和ys.
示例:foo [1..3] [4..6]应该返回
[[f 1 4,f 1 5,f 1 6],
[f 2 4,f 2 5,f 2 6],
[f 3 4,f 3 5,f 3 6]]
我目前的做法是
foo = traverse . flip . traverse . flip
这是有效的,但我想知道是否有其他方法或预先定义的组合器可以更好地完成(或者甚至可以合成,以便它可以很容易地扩展到三元或n元函数)
例如:如果我不想要一个结果网格而只需要一个结果列表,我可以编写f <$> xs <*> ys,这是简洁的,使用预定义的组合器,并以明显的方式推广到n-ary函数.是否有类似简洁的方法来编写我的组合器？