有没有实现纯函数集的算法？
预期的操作将是union，intersection，difference，element ？，空？并毗邻。
不过，这些并不是硬性要求，我很乐意学习一种只实现其中一部分的算法。
问问题
2323 次
5 回答
5
您可以使用纯粹的功能映射实现，您只需忽略这些值。
请参阅http://hackage.haskell.org/packages/archive/containers/0.1.0.1/doc/html/Data-IntMap.html（链接自https://cstheory.stackexchange.com/questions/1539/whats- new-in-purely-functional-data-structures-since-okasaki )。
（旁注：有关功能数据结构的更多信息，请参阅http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504）
于 2012-05-15T02:02:10.200 回答
3
几乎所有数据结构都存在纯粹的功能实现。对于集合或映射，您通常使用某种形式的搜索树，例如红/黑树或 AVL 树。函数式数据结构的标准参考是 Okasaki 的书：
http://www.cambridge.org/gb/knowledge/isbn/item1161740/
通过他的论文可以免费获得其中的重要部分：
于 2012-05-15T07:10:26.903 回答
1
@ninjagecko 的答案中的链接很好。我最近关注的是 Clojure 中使用的持久数据结构，它们是函数式的、不可变的和持久的。
可以在这篇由两部分组成的博客文章中找到持久哈希映射的实现描述：
http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice/
http://blog.higher-order.net/2010/08/16/assoc-and-clojures-persistenthashmap-part-ii/
这些是在这个参考请求问题中找到的一些想法的实现（参见第一个答案，第一个条目） 。
从这些结构中产生的集合支持您需要的功能：
http://clojure.org/data_structures#Data Structures-Sets
剩下的就是浏览源代码并试着绕开它。
于 2012-05-15T03:16:24.700 回答
1
这是OCaml 中纯函数集的实现（它是 OCaml 的标准库）。
于 2012-05-15T06:43:06.823 回答
1
有没有实现纯函数集的算法？
您可以使用许多不同的纯函数数据结构来实现集合操作。有些比其他的具有更好的复杂性。
示例包括：
我们在哪里：
List Difference:
(\\) :: Eq a => [a] -> [a] -> [a]
该\\函数是列表差异（（非关联）。在 的结果中xs \\ ys，ys 的每个元素的第一次出现依次（如果有）已从 xs 中删除。因此
union :: Eq a => [a] -> [a] -> [a]
union 函数返回两个列表的列表并集。例如，
"dog" `union` "cow" == "dogcw"
第一个列表的重复项和元素将从第二个列表中删除，但如果第一个列表包含重复项，结果也会如此。它是 unionBy 的一个特例，它允许程序员提供他们自己的相等性测试。
intersect :: Eq a => [a] -> [a] -> [a]
intersect 函数获取两个列表的列表交集。例如，
[1,2,3,4] `intersect` [2,4,6,8] == [2,4]
如果第一个列表包含重复项，结果也会如此。
不可变集
可以设计更高效的数据结构来提高集合操作的复杂性。例如，Data.SetHaskell 中的标准库将集合实现为大小平衡的二叉树：
- Stephen Adams，“高效集合：平衡行为”，函数式编程杂志 3(4):553-562，1993 年 10 月，http ://www.swiss.ai.mit.edu/~adams/BB/ 。
这是什么数据结构：
data Set a = Bin !Size !a !(Set a) !(Set a)
| Tip
type Size = Int
产生复杂度：
- 并集、交集、差异：O(n+m)
于 2012-05-16T12:36:30.820 回答