是否有一个算法可以实现纯函数集合?
期望的操作包括并集,交集,差集,元素查询,空集查询和添加元素。
尽管这些不是硬性要求,但我很乐意学习仅实现其中一部分的算法。
是否有一个算法可以实现纯函数集合?
期望的操作包括并集,交集,差集,元素查询,空集查询和添加元素。
尽管这些不是硬性要求,但我很乐意学习仅实现其中一部分的算法。
http://www.cambridge.org/gb/knowledge/isbn/item1161740/
他的论文中有很多重要部分可以免费获取:
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
现在只需浏览源代码并尝试理解它即可。
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]
如果第一个列表包含重复项,则结果也将包含重复项。
不可变集合
可以设计更高效的数据结构来提高集合操作的复杂度。例如,Haskell中标准的Data.Set
库将集合实现为平衡二叉树:
这就是该数据结构:
data Set a = Bin !Size !a !(Set a) !(Set a)
| Tip
type Size = Int
产生复杂度: