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

Question

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

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))))))

这是完整的算法，它甚至会成为最终实际代码的一部分，所以它也不是真正的伪代码。single-node?，make-node，insert-sorted没有定义，在Scheme中你会得到一个错误，但在CL中你可以实际使用它，它会跳转到调试器，在那里你会被问到是否要定义其中的一些，所以你基本上会在你执行的过程中实现缺少的部分，并继续执行，直到一切都完成。

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

Answer 2

如果我用函数风格的伪代码编写一个算法，那么我可能会混合和匹配语言，但将始终如一地使用：

• let-bound variables
• function application
• maps和folds

以哈希函数为例：

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