问题标签 [purely-functional]

我正在解决一个这样的编程练习：

一个文件包含一个正整数和之间的等式列表，每行一个，每行一个以分号结尾，没有空格。这些平等可能是对的，也可能是错的。例如，考虑以下文件：

编写一个程序，将文件名作为第一个参数并输出正确行数的比率。例如，给定上面的文件，程序应该输出 0.75。

我在 Scala 中的解决方案如下，它可以工作，但我正在寻找一种没有 var 的方法来重写它。

我试图把那个 foreach 变成一张地图，像这样：

编译器抱怨：

我想计算具有O(1)复杂性和O(n_max)预处理的第 n 个斐波那契数。

为此，我需要像下面的 C++ 代码一样存储先前计算的值：

但它依赖于 Elm 中不允许的副作用。

有人可以举一个简单的例子，其中 state monad 比直接传递 state 更好吗？

对比

我记得看过一个演示文稿，其中 SPJ 说懒惰的评估迫使他们保持 Haskell 的纯净（或类似的东西）。我经常看到许多 Haskellers 也这么说。

所以，我想了解惰性评估策略是如何迫使他们保持 Haskell 纯净而不是严格的评估策略？

纯 函数是类似于数学函数的函数，其中没有与“现实世界”的交互，也没有副作用。从更实际的角度来看，这意味着纯函数不能：

• 打印或以其他方式显示消息
• 随意
• 取决于系统时间
• 更改全局变量
• 和别的

所有这些限制使得对纯函数的推理比对非纯函数的推理更容易。大多数函数应该是纯函数，这样程序可以减少错误。

在像 Haskell 这样具有庞大类型系统的语言中，读者可以从一开始就知道函数是纯函数还是非纯函数，从而使后续阅读变得更容易。

在 Python 中，这个信息可以通过@pure放在函数顶部的装饰器来模拟。我也希望那个装饰器能够真正做一些验证工作。我的问题在于这样一个装饰器的实现。

现在，我只是在函数的源代码中查找流行语，例如globalor randomor print，如果找到其中一个，我会抱怨。

然而，这感觉就像一个奇怪的黑客，可能会也可能不会取决于你的运气，你能帮我写一个更好的装饰器吗？

在他关于流的介绍性章节中，Okasaki 提供了 2 种drop关于流的实现。

他明确提到第二个更有效（并且两者具有相同的语义），但我似乎无法弄清楚为什么一个比另一个更有效。任何见解将不胜感激。

当我在阅读SDLhaskell的文档时，我发现一些函数不可避免地会修改它的输入。例如，blitSurface将目标表面作为输入，但在函数内更新。现在，概括问题，如果我有一个函数f :: a -> IO a，如果我在函数内部修改它会破坏组合a吗？怎么样f :: IO a -> IO a？怎么样a -> IO ()？那么IO a -> IO ()呢？

考虑到blitSurface实际上是一个外来函数的情况，并且每帧制作一个新曲面听起来效率不高，这些函数是难以避免的。这样的功能会导致更大范围的问题吗？例如，以fModifySurface :: Surface -> IO ()which does 破坏性更新为例：

上面的代码中是否有任何意想不到的语义？如果是这样，利用改变输入的外部函数的最佳方法是什么？

我有一个图，它被实现为连接任意节点的边列表，其数据类型定义如下。

我将如何执行纯粹的功能性深度优先搜索，同时避免陷入循环？我不太清楚如何在保持纯粹功能的同时跟踪所有访问过的节点。答案可能是微不足道的，出于某种原因我在概念上没有掌握。

这段 C 代码在概念上可以描述为创建一个与输入数组相同但以 1 作为第一个元素的新数组：

这是一个纯函数（wink wink nudge nudge），只要不对输入数组及其元素进行进一步引用。C 类型系统不会为我们强制执行，但原则上似乎可以强制执行。

gcc 生成的代码简单高效：

我们的函数通过在恒定时间内创建一个全新的数组并且不使用额外的内存来实现看似不可能的事情。好的。可以编写一个具有类似数组输入和输出的 Haskell 函数，并且可以用类似的代码有效地实现吗？有没有办法表达“这是对该变量的最后引用”，以便纯函数可以在幕后蚕食变量？

如果函数被内联，那么这里不需要发生任何有趣的事情，所以我们假设调用者和函数将分别编译。

这篇文章是识字的Haskell。只需放入“pad.lhs”之类的文件ghci即可运行它。

好的，所以我能够弄清楚如何ST用纯代码表示 monad。首先，我们从引用类型开始。它的具体值并不重要。最重要的是它PT s a不应该与任何其他类型同构forall s。（特别是，它应该与 none()或同构Void。）

的种类s是*->*，但现在这并不重要。对于我们所关心的一切，它可能是多品种的。

很直接。AndThen允许我们将其用作Monad. 您可能想知道return是如何实现的。这是它的 monad 实例（它只遵守关于 的 monad 法则，runPF稍后将定义）：

现在我们可以定义fib为一个测试用例。

它键入检查。欢呼！现在，我能够将其转换为ST（我们现在明白为什么s必须这样做了* -> *）

现在我们可以定义一个完全PT不引用的函数来运行ST：

runPF $ fib 7给出13，这是正确的。

我的问题是我们可以在runPF没有参考ST的情况下定义使用吗？

有没有一种纯粹的定义方式runPF？PTRef的定义完全不重要；无论如何，它只是一个占位符类型。它可以重新定义为使其工作的任何东西。

如果你不能纯粹地定义runPF，请证明它不能。

性能不是问题（如果是，我不会让每个return人都有自己的参考）。

我认为存在类型可能有用。

注意：如果我们假设它a是可动态的，那是微不足道的。我正在寻找一个适用于所有人的答案a。

注意：事实上，答案甚至不一定与PT. 它只需要像ST不使用魔法一样强大。（从转换(forall s. PT s)是一种测试答案是否有效。）