问题标签 [purely-functional]

在纯函数式语言中，数据是不可变的。使用引用计数，创建引用循环需要更改已创建的数据。似乎纯函数式语言可以使用引用计数而不必担心循环的可能性。是对的吗？如果是这样，他们为什么不呢？

我知道在许多情况下引用计数比 GC 慢，但至少它减少了暂停时间。在暂停时间不好的情况下，可以选择使用引用计数。

作为 Haskell 的一个练习，我正在尝试实现堆排序。堆通常在命令式语言中实现为数组，但这在纯函数式语言中效率非常低。因此，我查看了二进制堆，但到目前为止我发现的所有内容都从命令式的角度描述了它们，并且所呈现的算法很难转化为功能设置。如何用 Haskell 等纯函数式语言高效地实现堆？

编辑：高效我的意思是它仍然应该在 O(n*log n) 中，但它不必击败 C 程序。另外，我想使用纯函数式编程。在 Haskell 中这样做还有什么意义？

是否可以在 C++ 中编写不纯的模板？也就是说，一个模板有时会为相同的模板参数提供不同的结果类型或 int。例如，是否可以编写一个模板，有时在Foo<T>哪里Foo<int>::type，有时char在哪里float？Foo<T>或者Foo<double>::my_static_const_int有时是 10 有时是 20的模板？

目前，我知道将副作用集成到纯函数式编程语言中的以下方法：

• 效果系统
• 继续
• 独特的类型
• 单子

单子经常被认为是最有效和最通用的方法。

还存在哪些其他方法？他们如何比较？

我有一个java.util.HashMap对象m（调用 Java 代码的返回值），我想获得一个带有附加键值对的新映射。

如果m是 Clojure 地图，我可以使用：

但是尝试一下HashMap会给出：

java.lang.ClassCastException：java.util.HashMap 无法转换为 clojure.lang.Associative

没有运气seq：

java.lang.ClassCastException：clojure.lang.IteratorSeq 不能转换为 clojure.lang.Associative

我设法做到这一点的唯一方法是使用HashMap's own put，但这会返回void，所以我必须明确返回m：

这不是惯用的 Clojure 代码，而且我正在修改m而不是创建新地图。

如何以HashMap更接近 Clojure 的方式使用？

跳过列表（Pugh，1990）为排序字典提供了对数时间操作，如搜索树，但跳过列表更适合并发更新。

是否可以创建一个高效的纯功能并发跳过列表？如果没有，是否有可能创建任何一种高效的纯功能并发排序字典？

有大量关于数据结构的文本，以及数据结构代码库。我知道纯函数式数据结构更容易推理。但是，我很难理解在实用代码中使用纯函数式数据结构（使用或不使用函数式编程语言）相对于命令式对应物的现实世界优势。有人可以提供一些纯函数式数据结构具有优势的真实案例吗？为什么？

像我使用data_structure_name in programming_language来做应用程序这样的例子，因为它可以做某些事情。

谢谢。

PS：我所说的纯函数式数据结构和持久化数据结构是不一样的。持久化数据结构是不会改变的数据结构？？另一方面，纯功能数据结构是一种纯粹操作的数据结构。

像Java 的弱哈希映射这样的弱哈希表使用弱引用来跟踪垃圾收集器对无法访问的键的集合，并从集合中删除与该键的绑定。弱哈希表通常用于实现从图中的一个顶点或边到另一个的间接寻址，因为它们允许垃圾收集器收集图的不可达部分。

这种数据结构是否存在纯粹的功能等价物？如果没有，如何创建一个？

这似乎是一个有趣的挑战。内部实现不可能是纯粹的，因为它必须收集（即变异）数据结构以删除无法访问的部分，但我相信它可以为用户提供一个纯粹的界面，用户永远无法观察到杂质，因为它们只影响数据的一部分根据定义，用户无法再访问的结构。

这些术语的定义似乎确实 不同，但我一直认为一个暗示另一个；我想不出任何情况下表达式是引用透明但不纯的，反之亦然。

维基百科为这些概念维护了单独的文章，并说：

从参考透明度：

如果表达式中涉及的所有函数都是纯函数，则表达式是引用透明的。此外，如果某些不纯函数的值被丢弃并且它们的副作用微不足道，则可以将它们包含在表达式中。

从纯表达式：

纯函数是构造纯表达式所必需的。[...] 纯表达式通常被称为引用透明的。

我发现这些陈述令人困惑。如果所谓的“不纯函数”的副作用微不足道，以至于不允许在不实质性更改程序的情况下不执行它们（即用它的值替换对此类函数的调用），那么它就好像它是纯的一样第一，不是吗？

有没有一种更简单的方法来理解纯表达式和引用透明表达式之间的区别（如果有的话）？如果存在差异，将不胜感激提供一个清楚地证明它的示例表达式。

在纯粹的函数式语言中，不能仍然定义一个“赋值”运算符，比如“<-”，这样命令，比如“i <- 3”，而不是直接分配不可变变量 i，会创建整个当前调用堆栈的副本，​​除了在新调用堆栈中将 i 替换为 3，并从该点开始执行新调用堆栈？鉴于没有实际更改数据，根据定义，这是否仍被视为“纯功能性”？当然编译器会简单地进行优化以简单地将 3 分配给 i，在这种情况下，命令式和纯函数式有什么区别？