pea*_*kit 62 recursion functional-programming scala tail-recursion
我将介绍函数式编程[FP](使用Scala).从我最初的学习中得出的一点是,FP很大程度上依赖于递归.而且似乎在纯 FP中,执行迭代的唯一方法是编写递归函数.
由于递归的大量使用似乎FPs不得不担心的下一件事StackoverflowExceptions通常是由于长缠绕递归调用.通过引入一些优化(@tailrec从Scala v2.8开始维护堆栈帧和注释中的尾递归相关优化)来解决这个问题
有人可以请教我为什么递归对函数式编程范式如此重要？如果我们迭代地执行某些操作,那么函数式编程语言的规范中是否会出现"违反"的内容？如果是,那么我也很想知道这一点.
PS:请注意,我是函数式编程的新手,所以如果他们解释/回答我的问题,请随时向我指出现有资源.另外我也明白Scala特别为迭代的东西提供支持.
Cap*_*liC 45
Church Turing论文强调了不同可计算性模型之间的等价性.
使用递归我们在解决某些问题时不需要可变状态,这使得可以用更简单的术语指定语义.因此,从形式上讲,解决方案可以更简单.
我认为Prolog比函数式语言更好地表示递归的有效性(它没有迭代),以及我们在使用它时遇到的实际限制.
Val*_*lle 35
纯函数编程意味着编程没有副作用.这意味着,如果你编写一个循环,你的循环体不会产生副作用.因此,如果您希望循环执行某些操作,则必须重用上一次迭代的结果并为下一次迭代生成一些内容.因此,循环体是一个函数,将先前执行的结果作为参数,并使用自己的结果调用自身进行下一次迭代.与直接为循环编写递归函数相比,这没有太大的优势.
一个不做一些微不足道的程序将不得不在某些时候迭代某些事情.对于函数式编程,这意味着程序必须使用递归函数.
Mag*_*off 20
导致您以递归方式执行操作的要求的特性是不可变的变量.
考虑一个简单的函数来计算列表的总和(伪代码):
fun calculateSum(list):
sum = 0
for each element in list: # dubious
sum = sum + element # impossible!
return sum
现在,element列表的每次迭代都是不同的,但是我们可以重写它以使用foreach带有lambda参数的函数来解决这个问题:
fun calculateSum(list):
sum = 0
foreach(list, lambda element:
sum = sum + element # impossible!
)
return sum
但是,sum在每次运行lambda时,必须改变变量的值.这在具有不可变变量的语言中是非法的,因此您必须以不改变状态的方式重写它:
fun calculateSum([H|T]):
return H + calculateSum(T)
fun calculateSum([]):
return 0
现在,这个实现需要大量推送和弹出调用堆栈,并且所有小型操作都会执行此操作的程序不会很快运行.因此,我们将其重写为尾递归,因此编译器可以进行尾调用优化:
fun calculateSum([H|T], partialSum):
return calculateSum(T, H + partialSum)
fun calculateSum([], partialSum):
return partialSum
fun calculateSum(list):
return calculateSum(list, 0)
当然,如果你想无限循环,你绝对需要一个尾递归调用,否则它会堆栈溢出.
@tailrecScala中的注释是一个工具,可以帮助您分析哪些函数是尾递归的.您声称"此函数是尾递归",然后编译器可以告诉您是否有误.这相对于其他功能的语言,因为机器运行时,JVM不支持尾调用优化以及Scala中是特别重要的,所以它是不可能得到尾调用优化的斯卡拉在所有你会得到相同的情况下它用其他功能语言.
TL; DR:递归是用来处理归纳定义的数据,这是普遍存在的.
当您在更高级别的抽象上操作时,递归是很自然的.功能编程不只是用函数编码; 它是关于在更高级别的抽象上运行,您自然地使用函数.使用函数,从任何有意义的上下文中重用相同的函数(再次调用它)是很自然的.
世界是通过重复相似/相同的构建块来构建的.如果你将一块布料切成两半,你就会有两块布料.数学归纳是数学的核心.我们人类计算(如1,2,3 ......).根据定义/构造该事物的相同情况,任何归纳定义的事物(例如,{数字来自1}是{1,数字来自2})自然地通过递归函数来处理/分析.
递归无处不在.无论如何,任何迭代循环都是伪装的递归,因为当你重新进入那个循环时,你再次重新进入同一个循环(只是可能有不同的循环变量).因此,它不像发明有关计算的新概念,更像是发现基础,并使其明确.
因此,递归是很自然的.我们只写下一些关于我们问题的定律,一些涉及我们定义的函数的方程式保留了一些不变量(假设函数是连贯定义的),用简化的术语重新指定问题,瞧!我们有解决方案.
一个例子,一个计算列表长度的函数(一个归纳定义的递归数据类型).假设它被定义,并且令人惊讶地返回列表的长度.它必须遵守哪些法律？在什么简化问题的情况下保留了什么不变量？
最直接的是将列表分开到其头元素,其余 - 也就是列表的尾部(根据列表的定义/构造方式).法律是,
length (x:xs) = 1 + length xs
D'呃!但那个清单怎么样？一定是这样
length [] = 0
那么我们如何编写这样的函数呢？......等等......我们已经写好了!(在Haskell中,如果你想知道,函数应用程序由并置表示,括号仅用于分组,并且(x:xs)是包含x其第一个元素的列表,xs其余部分).
我们需要一种允许这种编程风格的语言就是它具有TCO(也许,有点豪华, TRMCO),所以没有堆栈爆炸,我们已经设置好了.
另一件事是纯度 - 代码变量和/或数据结构(记录字段等)的不变性.
这样做,除了让我们的思想不必跟踪什么在改变什么时,它是否在我们的代码中明确显示时间,而不是隐藏在我们"变化"的可变变量/数据中.从现在开始,我们只能在命令式代码中"改变"一个变量的值- 我们不能很好地改变它过去的价值,我们可以吗？
因此,我们最终得到了记录更改历史记录的列表,代码中明确显示了更改:而不是x := x + 2我们编写let x2 = x1 + 2.它使代码的推理变得如此简单.
要在TCO的尾递归环境中解决不变性问题,请考虑length在累加器参数范例下对上述函数进行尾递归重写:
length xs = length2 0 xs -- the invariant:
length2 a [] = a -- 1st arg plus
length2 a (x:xs) = length2 (a+1) xs -- length of 2nd arg
这里TCO意味着调用帧重用,除了直接跳转,因此调用链length [1,2,3]可以看作实际上改变调用堆栈帧的对应于函数参数的条目:
length [1,2,3]
length2 0 [1,2,3] -- a=0 (x:xs)=[1,2,3]
length2 1 [2,3] -- a=1 (x:xs)=[2,3]
length2 2 [3] -- a=2 (x:xs)=[3]
length2 3 [] -- a=3 (x:xs)=[]
3
在纯语言中,没有任何值变异原语,表达变化的唯一方法是将更新的值作为参数传递给函数,以便进一步处理.如果进一步处理与之前相同,那么我们必须为此调用相同的函数,将更新后的值作为参数传递给它.这就是递归.
以下内容使得计算参数列表长度的整个历史记录显而易见(如果需要,可以重用):
length xs = last results
where
results = length3 0 xs
length3 a [] = [a]
length3 a (x:xs) = a : length3 (a+1) xs
在Haskell中,这可以被称为保护递归或核心运动(至少我认为是).
我认为有两个属性对函数式编程至关重要:
函数是一等成员(只有相关的,因为要使它有用,需要第二个属性)
函数是纯函数,即使用相同参数调用的函数返回相同的值.
现在,如果你以命令式的方式编程,你必须使用赋值.
考虑一个for循环.它有一个索引,每次迭代时索引都有不同的值.因此,您可以定义一个返回此索引的函数.如果您将该功能调用两次,则可能会得到不同的结果.从而打破了原则2.
如果你违反原则否2.传递函数(原则1)会变得非常危险,因为现在函数的结果可能取决于调用函数的时间和频率.
递归中没有"特殊".它是编程和数学中广泛使用的工具,仅此而已.但是,功能语言通常是简约的.它们确实引入了许多花哨的概念,如模式匹配,类型系统,列表理解等等,但它只不过是非常通用且非常强大但简单而原始的工具的语法糖.这个工具是:函数抽象和函数应用程序.这是有意识的选择,因为语言核心的简单性使得对它的推理变得更加容易.它还使编写编译器变得更容易.根据这个工具描述循环的唯一方法是使用递归,因此命令式程序员可能认为,函数式编程是关于递归的.事实并非如此,只需要模仿那些不能将这种语法糖放在goto语句之上的那些花哨的循环,因此这是他们坚持的第一件事.
需要(可以是间接)递归的另一点是处理递归定义的数据结构.最常见的例子是listADT.在FP中,它通常像这样定义data List a = Nil | Branch a (List a).由于这里ADT的定义是递归的,因此它的处理函数也应该是递归的.同样,这里的递归也不是特别的:以递归方式处理这种ADT在命令式和函数式语言中都是自然的.好吧,如果列表式ADT命令式循环仍然可以采用,但在不同的树状结构的情况下,他们不能.
所以递归没有什么特别之处.它只是另一种类型的函数应用程序.但是,由于现代计算系统的限制(来自C语言中制作不当的设计决策,这是事实上的标准跨平台汇编程序),即使函数调用是尾调用,它们也无法无限嵌套.由于它的函数式编程语言设计者必须要么允许有限尾调用尾递归(斯卡拉)或使用像trampoling复杂的技术(旧GHC代码生成),或直接编译成汇编(GHC现代代码生成).
TL; DR:在FP中没有任何特殊的递归,至少在IP中没有,但是,由于JVM的限制,尾递归是scala中允许的唯一类型的尾调用.
避免副作用是函数式编程的支柱之一(另一个是使用高阶函数).
想象一下如何在不依赖突变的情况下使用命令式流控制.可能吗？
当然for (var i = 0; i < 10; i++) ...取决于变异(i++).实际上,任何条件循环结构都可以.在while (something) ...该something将取决于一些可变的状态.当然,while (true) ...不使用突变.但如果你想要退出那个循环,你需要一个if (something) break.实际上,尝试考虑除了不依赖于突变的递归之外的(非无限)循环机制.
怎么样for (var x in someCollection) ...？现在我们越来越接近函数式编程了.该x可被认为是一个参数的循环体.重用名称与重新分配值不同.也许在循环体中,你将yield return价值观视为x(无变异)的表达.
完全相同,你可以将for循环体移动到函数体中foo (x) ...,然后someCollection使用更高阶函数将其映射- 用类似的东西替换你的循环结构Map(foo, someCollection).
但是,如何在Map没有变异的情况下实现库函数？好吧,当然使用递归!它已经为你完成了.一旦开始使用第二类高阶函数来替换循环结构,就必须自己实现递归函数.
此外,通过尾调用优化,递归定义等同于迭代过程.您可能也喜欢这篇博文:http://blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx