有人可以将此(plt)Scheme代码重写为Clojure吗？
(define (f n)
(printf "(f ~a)~n" n)
(g n))
(define (g n)
(printf "(g ~a)~n" n)
(h n))
(define (h n)
(printf "(h ~a)~n" n)
(f (+ n 1)))
以这种方式不会将程序f,g和h一起折叠并允许代码无限期地运行而不会崩溃？
我刚刚开始使用VS2010学习F#,下面是我第一次尝试生成Fibonacci系列.我要做的是建立一个小于400的所有数字的列表.
let fabList =
let l = [1;2;]
let mutable a = 1
let mutable b = 2
while l.Tail < 400 do
let c = a + b
l.Add(c)
let a = b
let b = c
我的第一个问题是,在最后一个语句中,我在最后一行收到错误消息"表达式中此点或之前的不完整结构化构造".我不明白我在这里做错了什么.
虽然这似乎是以相当有效的方式(从c ++/C#程序员)构建列表的明显方式,但从我对f#的了解很少,这似乎不是正确的方法来执行程序.这种感觉我是否正确？
在最近的StackOverflow答案中,我给出了以下递归代码:
def retry[T](n: Int)(fn: => T): T = {
try {
fn
} catch {
case e if n > 1 =>
retry(n - 1)(fn)
}
}
如果我添加@tailrec注释,我得到:
无法优化@tailrec带注释的方法重试:它包含一个不在尾部位置的递归调用.
我能够破解尾部递归替代方案,但我仍然想知道为什么这没有优化.为什么不？
F#作为一种语言非常适合编写语言解释器或编译器,但是,有一件事情让我们不知所措:StackOverflowException.
众所周知,无法捕获SO异常,无法从中恢复.防止这种异常的一种显而易见的技术是在你进行时计算堆栈的深度.开销,是的,但是可行,也许在每个功能中都没有必要.
使用F#,这种技术虽然没有带来太多好处.我们在解释器的动态生成表达式中大量使用尾调用优化技术.我们在SO异常中遇到的问题是:
只是增加堆栈大小不会有足够的帮助,我们希望给用户一个可记录的错误,最好是由调用应用程序捕获.为此,我们需要能够手动抛出异常,这使它可以捕获.但我们如何确定合适的时机？
更新:
Hans Passant在这里正确地提出了可预测性.但是,使用此DSL的程序员期望(某些)调用获得TCO,因此他们不希望有强大的堆栈限制.他们知道自己在做什么.尽管如此,他们的程序仍然需要能够优雅地消亡,至少在任何调用应用程序(即使用我们的库的C#程序)都不会受到损害的情况下.
对于工作中的参数优化问题,我写了一个遗传算法来找到一些好的设置,因为蛮力解决方案是不可行的.不幸的是,当我早上回来时,大部分时间我都会被送到StackOverflowException.
我已经使用F#已经有一段时间了所以我知道TCO和需要带累加器参数的函数,并且通常使用该形式.
经过大量的搜索,我认为我能够找到触发异常的代码:
breedPopulation alive |> simulate (generation + 1) lastTime ewma
breedPopulation从当前个体中生成新一代alive.然后通过调用开始下一轮/生成simulate.当我看到反汇编(总noob)时,我发现了一些pop和a ret,所以它看起来不像是对我的常规(非尾部)调用.
mov rcx,qword ptr [rbp+10h]
mov rcx,qword ptr [rcx+8]
mov rdx,qword ptr [rbp-40h]
cmp dword ptr [rcx],ecx
call 00007FFA3E4905C0
mov qword ptr [rbp-0F0h],rax
mov r8,qword ptr [rbp-0F0h]
mov qword ptr [rbp-80h],r8
mov r8,qword ptr [rbp-78h]
mov qword ptr [rsp+20h],r8
mov r8d,dword ptr [rbp+18h]
inc r8d
mov rdx,qword ptr [rbp+10h]
mov r9,qword ptr [rbp-20h]
mov rcx,7FFA3E525960h
call 00007FFA3E4A5040 …好的,只是在F#中,这就是我现在理解的方式:
有些问题本质上是递归的(构建或读出树结构只能命名一个)然后你使用递归.在这些情况下,您最好使用尾递归来使堆栈中断
有些语言是纯粹的功能,所以你必须使用递归而不是while循环,即使问题不是递归的
所以我的问题是:既然F#也支持命令式范式,你会在F#中使用尾递归来解决那些不是自然递归的问题吗？特别是因为我已经读过编译器重新认识尾递归并且只是在while循环中转换它？
如果是这样:为什么？
我想知道为什么
Prelude> head $ reverse $ [1..10000000] ++ [99]
99
不会导致堆栈溢出错误.前奏中的++似乎是直接的,非尾递归的:
(++) :: [a] -> [a] -> [a]
(++) [] ys = ys
(++) (x:xs) ys = x : xs ++ ys
编辑:最初,我认为这个问题与前奏中定义的++的方式有关,特别是对于重写规则,因此问题继续如下.讨论向我表明情况并非如此.我现在认为一些懒惰的评估效果导致代码在没有堆栈溢出的情况下运行,但我不太明白如何.
所以就这样,它会遇到堆栈溢出,对吧？所以我认为它可能与遵循++定义的ghc魔法有关:
{ - #RULES"++"[~1] forall xs ys.xs ++ ys = augment(\ cn - > foldr cn xs)ys# - }
*这有助于避免堆栈溢出吗？有人可以提供一些暗示这段代码中发生了什么吗？**
R是否支持正确的尾递归,哪里可以找到关于此的文档？
我想知道是否有一些通用方法来转换"正常"递归foo(...) + foo(...)作为最后一次调用尾递归.
例如(scala):
def pascal(c: Int, r: Int): Int = {
if (c == 0 || c == r) 1
else pascal(c - 1, r - 1) + pascal(c, r - 1)
}
函数式语言的一般解决方案,用于将递归函数转换为尾部调用等效函数:
一种简单的方法是将非尾递归函数包装在Trampolinemonad中.
def pascalM(c: Int, r: Int): Trampoline[Int] = {
if (c == 0 || c == r) Trampoline.done(1)
else for {
a <- Trampoline.suspend(pascal(c - 1, r - 1))
b <- Trampoline.suspend(pascal(c, r - 1))
} yield a + b
} …我一直在阅读文章,描述如何通过使用尾递归版本来减少快速排序的空间复杂性,但我无法理解这是怎么回事.以下是两个版本:
QUICKSORT(A, p, r)
q = PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
TAIL-RECURSIVE-QUICKSORT(A, p, r)
while p < r
q = PARTITION(A, p, r)
TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
p = q+1
(来源 - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html)
据我所知,这两个都会导致数组的左半部分和右半部分的递归调用.在这两种情况下,一次只处理一半,因此在任何时候只有一个递归调用将使用堆栈空间.我无法看到尾递归快速排序如何节省空间.
上面的伪代码取自文章 - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html文章中 提供的解释让我更加困惑 -
Quicksort对给定的子数组进行分区并继续递归两次; 一个在左子阵列上,一个在右侧.这些递归调用中的每一个都需要其自己的堆栈空间流.此空间用于在某种递归级别存储数组的索引变量.如果我们想象这是从执行的开始到结束发生的,我们可以看到堆栈空间在每一层加倍.
那么Tail-Recursive-Quicksort如何修复所有这些呢？
好吧,我们现在只对一个子阵列进行递归,而不是在两个子阵列上递归.这消除了在每个执行层加倍堆栈空间的需要.我们通过使用while循环作为执行相同任务的迭代控件来解决这个问题.我们只需更改同一组变量并对新变量使用单个递归调用,而不是需要堆栈为两个递归调用保存变量集.
在常规快速排序的情况下,我没有看到堆栈空间在每个执行层都是如何加倍的.
注意: - 文章中没有提到编译器优化.