如何为函数式编程语言编写伪代码？

Question

如何编写Scheme或Haskell等函数式编程语言的伪代码？ 我搜索到的所有内容都显示了C风格或Python风格的伪代码。

- Vasantha Ganesh

---

我认为这高度取决于你想为哪种函数式语言编写伪代码。Haskell、OCaml和F#与Erlang、Clojure/Lisp的方法完全不同。因此，伪代码看起来会不同。对于Haskell，我主要会编写类型签名，并用散文解释底层算法。至于动态语言，我没有足够的实践经验给你任何提示。 - epsilonhalbe

你为什么想要写伪代码？是有人说“给我看看伪代码”，还是你试图理解如何以函数式风格设计代码？如果是后者，那么伪代码可能不是正确的方法。更多关于你问题的背景信息会很有用。 - Paul Johnson

通常（虽然不总是），函数式代码非常紧凑和高级，因此在小空间中可以容纳整个算法，从而不需要伪代码。在我看来，当您拥有过于冗长的语法（这会损害理解力）或者想要跳过一些无聊的部分时（存根在这里也可以很好地工作），伪代码更有用。 - chi

如果我正在草拟一些Haskell代码，通常会省略明显的函数和方法定义（例如，没有详细信息的instance Sequence Seq），或者只有类型签名而没有代码的函数。我也不使用GHC编写它，因此如果我正在草拟某些复杂的东西，则某些类型可能会有点偏差。 - dfeuer

你知道他们会接受函数伪代码吗（不过这可能是怎么工作的）？有些老师对他们想要的伪代码格式非常挑剔。你应该找出他们想要什么。 - David Young

Answer 1

在SICP和其他教程中，你会遇到一种叫做乐观编程的东西。与其使用伪代码，你只需命名事物并提供它们可能带有的参数。因此，想象一下你想从按频率从低到高排序的节点列表中制作哈夫曼树：

(define (huffman nodes)
  (if (single-node? nodes)
      (first nodes)
      (let ([new-node
             (make-node (first  nodes)
                        (second nodes))])
        (huffman (insert-sorted new-node        
                                (cddr nodes))))))

这是完整的算法，它甚至将成为最终代码的一部分，因此它不是伪代码。在Scheme中未定义single-node？、make-node和insert-sorted会导致错误，但在CL中，您实际上可以使用它，并且它会跳转到调试器，询问是否要定义其中一些内容，因此您可以随时实现缺失的部分，并继续执行直到完成所有操作。

我想在Haskell或其他任何编程语言中，不仅限于函数式编程，都可以进行这种乐观的编程 - 当然是在您正在实现的语言中。最终结果可能会有小变化，但不会比其他重构大。

- Sylwester

Answer 2

如果我用函数式伪代码编写算法，那么我可能会混合使用不同的语言，但始终会使用:

• let-bound变量
• 函数应用
• 映射和折叠

例如，考虑一个哈希函数：

hash data =
  let blocks = chunksOf blockSize (preprocess data)
  foldr updateContext initialContext blocks

- Thomas M. DuBuisson