功能编程中是否存在"算法"？

Question

如果在功能范例中实现,那么被要求记录软件的"算法"(例如,在设计规范中)是否毫无意义？每当我想到技术文档中的算法时,我都会想到一个带有一系列连续步骤的while循环.

查看算法的非正式字典含义:

在数学和计算机科学中,算法是计算的逐步过程.

"逐步"这个短语似乎违背了函数式编程的范式(正如我所理解的那样),因为与命令式程序相比,函数式程序在其假设的机器中没有时间意识.这个论点是否正确？或懒惰评估是否强制执行隐式时间组件,使其"一步一步"？

编辑 - 这么多好的答案,我选择最佳答案是不公平的:(感谢所有的观点,他们都做了很好的观察.

Answer 1

是的,算法仍然存在于函数式语言中,尽管它们并不总是与命令式算法相同.

功能语言不是使用基于状态来模拟步骤的"时间"的隐含概念,而是使用组合数据转换来完成它.作为一个非常好的示例,您可以将堆排序分为两部分:从列表转换为堆,然后从堆转换为列表.

您可以使用递归非常自然地对逐步逻辑进行建模,或者更好的是,使用现有的高阶函数来捕获您可以执行的各种计算.编写这些现有作品可能就是我所谓的"功能风格":你可以将你的算法表示为展开,然后是地图,然后是折叠.

通过模糊"数据结构"和"算法"之间的界限,懒惰使这更加有趣.像列表一样的惰性数据结构永远不必完全存在于内存中.这意味着您可以构建构建大型中间数据结构的函数,而无需实际使用所有空间或牺牲渐近性能.作为一个简单的例子,考虑这个定义factorial(是的,这是陈词滥调,但我无法想出更好的东西:/):

factorial n = product [1..n]

这有两个组成部分:第一,我们从生成一个列表1来n,然后我们把它折叠乘以(product).但是,由于懒惰,列表永远不会完全存在于内存中!我们在每个步骤中评估尽可能多的生成函数product,并且垃圾收集器在我们完成它们时回收旧单元.所以即使这看起来它需要O(n)内存,它实际上也会消失O(1).(好吧,假设数字都O(1)记忆了.)

在这种情况下,算法的"结构",即步骤序列,由列表结构提供.这里的列表更接近于for循环而不是实际列表!

因此,在函数式编程中,我们可以通过几种不同的方式将算法创建为一系列步骤:通过直接递归,通过组合转换(可能基于常见的高阶函数)或通过懒惰地创建和使用中间数据结构.

Answer 2

我想你可能误解了函数式编程范式.

无论您使用的是函数式语言(Lisp,ML,Haskell)还是命令式/过程式(C/Java/Python),您都要指定操作及其顺序(有时可能没有指定顺序,但这是一个副作用).

功能范例对您可以做的事情设置了某些限制(例如,没有副作用),这使得更容易推理代码(并且顺便说一句,更容易编写"足够智能编译器").

考虑,例如,阶乘的功能实现:

(defun ! (n)
  (if (zerop n)
      1
      (* n (! (1- n)))))

一旦可以很容易地看到执行的顺序:1 * 2 * 3 * .... * n以及n-1参数的乘法和减法这一事实 n.

计算机科学最重要的部分是要记住,语言只是与计算机交谈的手段.CS关于计算机不仅仅是天文学是关于望远镜的,算法是在抽象(图灵)机器上执行的,由我们面前的实际盒子模拟.

Answer 3

不,我认为如果你在功能上解决了问题并且你必须解决它,你提出的是两个独立的算法.每个都是算法.一种是功能算法,一种是命令式算法.关于函数式编程语言中的算法有很多书.

看起来你在这里遇到了技术性/语义学.如果要求您记录算法以解决问题,那么任何要求您的人都想知道您是如何解决问题的.即使它的功能,也会有一系列步骤来达到解决方案(即使是所有的懒惰评估).如果你可以编写代码来达到解决方案,那么你可以用伪代码编写代码,这意味着你可以根据我所关注的算法编写代码.

而且,既然你似乎对这里的定义非常感兴趣,我会以你的方式提出一个问题来证明我的观点.编程语言,无论是功能性的还是命令式的,最终都在机器上运行.对？必须告诉您的计算机一步一步的低级别指令才能运行.如果该陈述成立,那么每个高级计算机程序都可以用它们的低级指令来描述.因此,每个程序,无论是功能的还是命令的,都可以用算法来描述.如果您似乎无法找到描述高级算法的方法,那么输出字节码/汇编并根据这些说明解释您的算法