logo标签列表

纯函数式集合

algorithmdata-structuresfunctional-programmingsetreferential-transparency
3

是否有一个算法可以实现纯函数集合？

期望的操作包括并集，交集，差集，元素查询，空集查询和添加元素。

尽管这些不是硬性要求，但我很乐意学习仅实现其中一部分的算法。

5
您所描述的内容不构成算法，而是一种数据结构。这是否符合您的需求？ - David Kirby
你实际上想要实现/做什么，以及在什么情境下？ - Kzqai
你希望它在功能上是不可变的和一致的（在相同的集合上调用相同的函数会产生相同的结果），还是说它可能不包含状态（即使只是内部状态）？ - yamen
@yamen 不可变且持久化。使用记忆化并不是问题。 - didi
5个回答
3
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

现在只需浏览源代码并尝试理解它即可。

1

这里是OCaml中一个纯函数集合的实现（它是OCaml的标准库）。

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]

如果第一个列表包含重复项，则结果也将包含重复项。

不可变集合

可以设计更高效的数据结构来提高集合操作的复杂度。例如，Haskell中标准的Data.Set库将集合实现为平衡二叉树：

这就是该数据结构：

data Set a    = Bin !Size !a !(Set a) !(Set a)
              | Tip

type Size     = Int

产生复杂度：

  • 并集、交集、差集：O(n+m)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接