任何算法难题都可以以纯粹的功能方式实现吗?

时间:2021-10-24 22:04:07

I've been contemplating programming language designs, and from the definition of Declarative Programming on Wikipedia:

我一直在考虑编程语言设计,并从*上的声明性编程的定义:

This is in contrast from imperative programming, which requires a detailed description of the algorithm to be run.

这与命令式编程形成对比,命令式编程需要运行算法的详细描述。

and further down:

进一步向下:

... Any style of programming that is not imperative. ...

......任何不必要的编程风格。 ...

It then goes on to express that functional languages, because they are not imperative, are declarative by their very nature.

然后它继续表达功能语言,因为它们不是必要的,它们本质上是声明性的。

However, this makes me wonder, are purely functional programming languages able to solve any algorithmic problem, or are the constraints based upon what functions are available in that language?

但是,这让我想知道,纯函数式编程语言是否能够解决任何算法问题,还是基于该语言中可用函数的约束?

I'm mostly interested in general thoughts on the subject, although if specific examples can illustrate the point, I certainly welcome them.

我最感兴趣的是关于这个主题的一般想法,虽然如果具体的例子可以说明这一点,我当然欢迎他们。

8 个解决方案

#1


According to the Church-Turing Thesis ,

根据Church-Turing Thesis,

the three computational processes (recursion, λ-calculus, and Turing machine) were shown to be equivalent"

三个计算过程(递归,λ演算和图灵机)被证明是等价的“

where Turing machine can be read as "procedural" and lambda calculus as "functional".

其中图灵机可以读作“程序”,而lambda演算可以读作“功能”。

#2


Yes, Haskell, Erlang, etc. are Turing complete languages. In principle, you don't need mutable state to solve a problem, since you can always create a new object instead of mutating the old one. Of course, Brainfuck is also Turing complete. In other words, just because an algorithm can be expressed in a functional language doesn't mean it's not horribly awkward.

是的,Haskell,Erlang等是图灵完整的语言。原则上,您不需要可变状态来解决问题,因为您始终可以创建新对象而不是改变旧对象。当然,Brainfuck也是图灵完成的。换句话说,仅仅因为算法可以用函数式语言表达并不意味着它不是非常尴尬。

#3


OK, so Church and Turing provied it is possible, but how do we actually do something?

好吧,所以Church和Turing证明这是可能的,但我们如何做到呢?

Rewriting imperative code in pure functional style is an exercise I frequently assign to undergraduate students:

以纯函数式重写命令式代码是我经常分配给本科生的一项练习:

  • Each mutable variable becomes a function parameter
  • 每个可变变量都成为一个函数参数

  • Loops are rewritten using recursion
  • 循环使用递归重写

  • Each goto is expressed as a function call with arguments
  • 每个goto表示为带参数的函数调用

Sometimes what comes out is a mess, but often the results are surprisingly elegant. The only real trick is not to pass arguments that never change, but instead to let-bind them in the outer environment.

有时出来的是一团糟,但结果往往是惊人的优雅。唯一真正的诀窍是不传递永不改变的参数,而是将它们绑定在外部环境中。

#4


The big difference with functional style programming is that it avoids mutable state. Where imperative programming will typically update variables, functional programming will define new, read-only values.

功能样式编程的最大区别在于它避免了可变状态。在命令式编程通常会更新变量的情况下,函数式编程将定义新的只读值。

The main place where this will hit performance is with algorithms that use updatable arrays. An imperative implementation can update an array element in O(1) time, while the best a purely functional style of implementation can achieve is O(log N) (using a sorted tree).

这会影响性能的主要地方是使用可更新数组的算法。命令式实现可以在O(1)时间内更新数组元素,而最好的纯函数式实现可以实现O(log N)(使用排序树)。

Note that functional languages generally have some way to use updateable arrays with O(1) access time (e.g., Haskell provides this with its state transformer monad). However, this is arguably an imperative programming method... nothing wrong with that; you want to use the best tools for a particular job, after all.

注意,函数式语言通常有一些方法可以使用具有O(1)访问时间的可更新数组(例如,Haskell为其提供了状态变换器monad)。然而,这可以说是一种必要的编程方法......没有错;毕竟,你想为特定的工作使用最好的工具。

The functional style of O(log N) incremental array update is not all bad, though, as functional style algorithms seem to lend themselves well to parallellization.

然而,O(log N)增量数组更新的功能样式并不全是坏事,因为功能样式算法似乎很适合并行化。

#5


Too long to be posted as a comment on @SteveB's answer.

在@ SteveB的答案中发表评论太久了。

Functional programming and imperative programming have equal capability: whatever one can do, the other can do. They are said to be Turing complete. The functions that a Turing machine can compute are exactly the ones that recursive function theory and λ-calculus express.

功能编程和命令式编程具有相同的功能:无论人们能做什么,另一个都能做到。据说他们是图灵完整的。图灵机可以计算的函数正是递归函数理论和λ演算表达的函数。

But the Church-Turing Thesis, as such, is irrelevant. It asserts that any computation can be carried out by a Turing machine. This relates an informal idea - computation - to a formal one - the Turing machine. Nobody has yet found anything we would recognise as computation that a Turing machine can't do. Will someone find such a thing in future? Who can tell.

但是教会 - 图灵论文就是这样,无关紧要。它声称任何计算都可以由图灵机进行。这将非正式的想法 - 计算 - 与正式的想法 - 图灵机器联系起来。还没有人发现任何我们认为是图灵机无法做到的计算。将来有人会发现这样的事吗?谁能说出来。

#6


Using state monads you can program in an imperative style in Haskell.

使用状态monad,您可以在Haskell中以命令式编程。

So the assertion that Haskell is declarative by its very nature needs to be taken with a grain of salt. On the positive side it then is equivalent to imperative programming languages, also in a practical sense which doesn't completely ignore efficiency.

因此,Haskell本质上是声明性的断言需要花费一些时间。从积极的方面来说,它等同于命令式编程语言,在实际意义上也不完全忽略效率。

#7


While I completely agree with the answer that invokes Church-Turing thesis, this begs an interesting question actually. If I have a parallel computation problem (which is not algorithmic in a strict mathematical sense), such as multiple producer/consumer queue or some network protocol between several machines, can this be adequately modeled by Turing machine? It can be simulated, but if we simulate it, we lose the purpose why we have the parallelism in the problem (because then we can find simpler algorithm on the Turing machine). So what if we were not to lose parallelism inherent to the problem (and thus the reason why are we interested in it), we couldn't remove the notion of state?

虽然我完全赞同引用Church-Turing论文的答案,但这实际上引出了一个有趣的问题。如果我有一个并行计算问题(在严格的数学意义上不是算法),例如多个生产者/消费者队列或几台机器之间的某些网络协议,这可以通过图灵机充分建模吗?它可以被模拟,但是如果我们模拟它,我们就失去了为什么我们在问题中具有并行性的目的(因为那时我们可以在图灵机上找到更简单的算法)。那么,如果我们不失去问题所固有的并行性(因此我们对它感兴趣的原因),我们无法消除国家的概念呢?

#8


I remember reading somewhere that there are problems which are provably harder when solved in a purely functional manner, but I can't seem to find the reference.

我记得在某个地方读过,当以纯粹的功能性方式解决时,有些问题变得更难,但我似乎无法找到参考。

As noted above, the primary problem is array updates. While the compiler may use a mutable array under the hood in some conditions, it must be guaranteed that only one reference to the array exists in the entire program.

如上所述,主要问题是阵列更新。虽然编译器可能在某些条件下使用可变数组,但必须保证整个程序中只存在一个对该数组的引用。

Not only is this a hard mathematical fact, it is also a problem in practice, if you don't use impure constructs.

这不仅是一个很难的数学事实,如果你不使用不纯的结构,它在实践中也是一个问题。

On a more subjective note, stating that all Turing complete languages are equivalent is only true in a narrow mathematical sense. Paul Graham explores the issue in Beating the Averages in the section "The Blub Paradox."

在一个更主观的说明中,声明所有图灵完整语言都是等价的,这只是在狭义的数学意义上。 Paul Graham在“The Blub Paradox”一节中探讨了击败平均值的问题。

Formal results such as Turing-completeness may be provably correct, but they are not necessarily useful. The travelling salesman problem may be NP-complete, and yet salesman travel all the time. It seems they don't feel the need to follow an "optimal" path, so the theorem is irrelevant.

诸如图灵完整性之类的正式结果可能是可证明的正确的,但它们并不一定有用。旅行商问题可能是NP完全的,但销售人员一直在旅行。似乎他们觉得不需要遵循“最优”路径,所以这个定理是无关紧要的。

NOTE: I am not trying to bash functional programming, since I really like it. It is just important to remember that it is not a panacea.

注意:我不是想尝试功能编程,因为我真的很喜欢它。重要的是要记住,它不是灵丹妙药。

#1


According to the Church-Turing Thesis ,

根据Church-Turing Thesis,

the three computational processes (recursion, λ-calculus, and Turing machine) were shown to be equivalent"

三个计算过程(递归,λ演算和图灵机)被证明是等价的“

where Turing machine can be read as "procedural" and lambda calculus as "functional".

其中图灵机可以读作“程序”,而lambda演算可以读作“功能”。

#2


Yes, Haskell, Erlang, etc. are Turing complete languages. In principle, you don't need mutable state to solve a problem, since you can always create a new object instead of mutating the old one. Of course, Brainfuck is also Turing complete. In other words, just because an algorithm can be expressed in a functional language doesn't mean it's not horribly awkward.

是的,Haskell,Erlang等是图灵完整的语言。原则上,您不需要可变状态来解决问题,因为您始终可以创建新对象而不是改变旧对象。当然,Brainfuck也是图灵完成的。换句话说,仅仅因为算法可以用函数式语言表达并不意味着它不是非常尴尬。

#3


OK, so Church and Turing provied it is possible, but how do we actually do something?

好吧,所以Church和Turing证明这是可能的,但我们如何做到呢?

Rewriting imperative code in pure functional style is an exercise I frequently assign to undergraduate students:

以纯函数式重写命令式代码是我经常分配给本科生的一项练习:

  • Each mutable variable becomes a function parameter
  • 每个可变变量都成为一个函数参数

  • Loops are rewritten using recursion
  • 循环使用递归重写

  • Each goto is expressed as a function call with arguments
  • 每个goto表示为带参数的函数调用

Sometimes what comes out is a mess, but often the results are surprisingly elegant. The only real trick is not to pass arguments that never change, but instead to let-bind them in the outer environment.

有时出来的是一团糟,但结果往往是惊人的优雅。唯一真正的诀窍是不传递永不改变的参数,而是将它们绑定在外部环境中。

#4


The big difference with functional style programming is that it avoids mutable state. Where imperative programming will typically update variables, functional programming will define new, read-only values.

功能样式编程的最大区别在于它避免了可变状态。在命令式编程通常会更新变量的情况下,函数式编程将定义新的只读值。

The main place where this will hit performance is with algorithms that use updatable arrays. An imperative implementation can update an array element in O(1) time, while the best a purely functional style of implementation can achieve is O(log N) (using a sorted tree).

这会影响性能的主要地方是使用可更新数组的算法。命令式实现可以在O(1)时间内更新数组元素,而最好的纯函数式实现可以实现O(log N)(使用排序树)。

Note that functional languages generally have some way to use updateable arrays with O(1) access time (e.g., Haskell provides this with its state transformer monad). However, this is arguably an imperative programming method... nothing wrong with that; you want to use the best tools for a particular job, after all.

注意,函数式语言通常有一些方法可以使用具有O(1)访问时间的可更新数组(例如,Haskell为其提供了状态变换器monad)。然而,这可以说是一种必要的编程方法......没有错;毕竟,你想为特定的工作使用最好的工具。

The functional style of O(log N) incremental array update is not all bad, though, as functional style algorithms seem to lend themselves well to parallellization.

然而,O(log N)增量数组更新的功能样式并不全是坏事,因为功能样式算法似乎很适合并行化。

#5


Too long to be posted as a comment on @SteveB's answer.

在@ SteveB的答案中发表评论太久了。

Functional programming and imperative programming have equal capability: whatever one can do, the other can do. They are said to be Turing complete. The functions that a Turing machine can compute are exactly the ones that recursive function theory and λ-calculus express.

功能编程和命令式编程具有相同的功能:无论人们能做什么,另一个都能做到。据说他们是图灵完整的。图灵机可以计算的函数正是递归函数理论和λ演算表达的函数。

But the Church-Turing Thesis, as such, is irrelevant. It asserts that any computation can be carried out by a Turing machine. This relates an informal idea - computation - to a formal one - the Turing machine. Nobody has yet found anything we would recognise as computation that a Turing machine can't do. Will someone find such a thing in future? Who can tell.

但是教会 - 图灵论文就是这样,无关紧要。它声称任何计算都可以由图灵机进行。这将非正式的想法 - 计算 - 与正式的想法 - 图灵机器联系起来。还没有人发现任何我们认为是图灵机无法做到的计算。将来有人会发现这样的事吗?谁能说出来。

#6


Using state monads you can program in an imperative style in Haskell.

使用状态monad,您可以在Haskell中以命令式编程。

So the assertion that Haskell is declarative by its very nature needs to be taken with a grain of salt. On the positive side it then is equivalent to imperative programming languages, also in a practical sense which doesn't completely ignore efficiency.

因此,Haskell本质上是声明性的断言需要花费一些时间。从积极的方面来说,它等同于命令式编程语言,在实际意义上也不完全忽略效率。

#7


While I completely agree with the answer that invokes Church-Turing thesis, this begs an interesting question actually. If I have a parallel computation problem (which is not algorithmic in a strict mathematical sense), such as multiple producer/consumer queue or some network protocol between several machines, can this be adequately modeled by Turing machine? It can be simulated, but if we simulate it, we lose the purpose why we have the parallelism in the problem (because then we can find simpler algorithm on the Turing machine). So what if we were not to lose parallelism inherent to the problem (and thus the reason why are we interested in it), we couldn't remove the notion of state?

虽然我完全赞同引用Church-Turing论文的答案,但这实际上引出了一个有趣的问题。如果我有一个并行计算问题(在严格的数学意义上不是算法),例如多个生产者/消费者队列或几台机器之间的某些网络协议,这可以通过图灵机充分建模吗?它可以被模拟,但是如果我们模拟它,我们就失去了为什么我们在问题中具有并行性的目的(因为那时我们可以在图灵机上找到更简单的算法)。那么,如果我们不失去问题所固有的并行性(因此我们对它感兴趣的原因),我们无法消除国家的概念呢?

#8


I remember reading somewhere that there are problems which are provably harder when solved in a purely functional manner, but I can't seem to find the reference.

我记得在某个地方读过,当以纯粹的功能性方式解决时,有些问题变得更难,但我似乎无法找到参考。

As noted above, the primary problem is array updates. While the compiler may use a mutable array under the hood in some conditions, it must be guaranteed that only one reference to the array exists in the entire program.

如上所述,主要问题是阵列更新。虽然编译器可能在某些条件下使用可变数组,但必须保证整个程序中只存在一个对该数组的引用。

Not only is this a hard mathematical fact, it is also a problem in practice, if you don't use impure constructs.

这不仅是一个很难的数学事实,如果你不使用不纯的结构,它在实践中也是一个问题。

On a more subjective note, stating that all Turing complete languages are equivalent is only true in a narrow mathematical sense. Paul Graham explores the issue in Beating the Averages in the section "The Blub Paradox."

在一个更主观的说明中,声明所有图灵完整语言都是等价的,这只是在狭义的数学意义上。 Paul Graham在“The Blub Paradox”一节中探讨了击败平均值的问题。

Formal results such as Turing-completeness may be provably correct, but they are not necessarily useful. The travelling salesman problem may be NP-complete, and yet salesman travel all the time. It seems they don't feel the need to follow an "optimal" path, so the theorem is irrelevant.

诸如图灵完整性之类的正式结果可能是可证明的正确的,但它们并不一定有用。旅行商问题可能是NP完全的,但销售人员一直在旅行。似乎他们觉得不需要遵循“最优”路径,所以这个定理是无关紧要的。

NOTE: I am not trying to bash functional programming, since I really like it. It is just important to remember that it is not a panacea.

注意:我不是想尝试功能编程,因为我真的很喜欢它。重要的是要记住,它不是灵丹妙药。