GHC默认会对以下函数执行尾调用优化吗？关于它的唯一奇怪的事情是它递归地定义了一个IO动作,但我不明白为什么这不是TCO.
import Control.Concurrent.MVar
consume :: MVar a -> [a] -> IO ()
consume _ [] = return ()
consume store (x:xs) = do putMVar store x
consume store xs
我正在尝试在OCaml中实现尾递归列表排序功能,我想出了以下代码:
let tailrec_merge_sort l =
let split l =
let rec _split source left right =
match source with
| [] -> (left, right)
| head :: tail -> _split tail right (head :: left)
in _split l [] []
in
let merge l1 l2 =
let rec _merge l1 l2 result =
match l1, l2 with
| [], [] -> result
| [], h :: t | h :: t, [] -> _merge [] t (h :: result)
| …最近,我正在学习F#.我尝试以不同的方式解决问题.像这样:
(*
[0;1;2;3;4;5;6;7;8] -> [(0,1,2);(3,4,5);(6,7,8)]
*)
//head-recursive
let rec toTriplet_v1 list=
match list with
| a::b::c::t -> (a,b,c)::(toTriplet_v1 t)
| _ -> []
//tail-recursive
let toTriplet_v2 list=
let rec loop lst acc=
match lst with
| a::b::c::t -> loop t ((a,b,c)::acc)
| _ -> acc
loop list []
//tail-recursive(???)
let toTriplet_v3 list=
let rec loop lst accfun=
match lst with
| a::b::c::t -> loop t (fun ls -> accfun ((a,b,c)::ls))
| _ -> accfun []
loop list (fun x -> …类型值如何:
type Tree =
| Node of int * Tree list
有一个值引用自己以功能方式生成的值吗？
对于Tree的合适定义,结果值应该等于以下Python代码中的x:
x = Tree()
x.tlist = [x]
编辑:显然需要更多解释.我正在尝试学习F#和函数式编程,所以我选择实现之前用其他语言编写的封面树.这里相关的是每个级别的点是下面级别的点的子集.结构在概念上达到了水平 - 无限.
在命令式语言中,节点具有包含其自身的子列表.我知道这可以在F#中强制执行.不,它不会在封面树算法的情况下创建无限循环.
披露:这出现在FsCheck中,这是我维护的F#随机测试框架.我有一个解决方案,但我不喜欢它.而且,我不明白这个问题 - 它只是被规避了.
一个相当标准的实现(monadic,如果我们要使用大词)序列是:
let sequence l =
let k m m' = gen { let! x = m
let! xs = m'
return (x::xs) }
List.foldBack k l (gen { return [] })
gen可以由选择的计算构建器替换.不幸的是,该实现消耗了堆栈空间,因此如果列表足够长,最终会堆栈溢出.问题是:为什么？我原则上知道foldBack不是尾递归,但是F#团队的聪明兔子已经在foldBack实现中绕过了它.计算构建器实现中是否存在问题？
如果我将实现更改为以下,一切都很好:
let sequence l =
let rec go gs acc size r0 =
match gs with
| [] -> List.rev acc
| (Gen g)::gs' ->
let r1,r2 = split r0
let y = g size r1
go gs' (y::acc) size r2
Gen(fun n r -> …我一直在谷歌搜索多年,仍然找不到答案.根据我的理解,如果调用者在try/catch和/或try/finally块中包装了调用,那么在.NET 4.5上运行的F#3.0将不会对递归方法使用尾递归.如果有一个try/catch或者try/finally几个级别的堆栈会是什么情况？
我试图搜索,但无法找到:函数的必要条件是什么,以便gcc优化尾递归？是否有任何参考或列表包含最重要的案例？由于这是版本特定的,我的兴趣是4.6.3或更高版本(越新越好).但事实上,任何具体的参考资料都将受到高度赞赏.
提前致谢!
我在F#中有一些代码在.net下工作正常但在Mono下溢出了堆栈.一个相关的问题是它似乎早在可能可用的堆栈空间耗尽之前就已经用完了(它以System.Threading.Thread(ts,1000000000)开头).据我所知,它死的折叠是尾递归的,堆栈跟踪看起来好像没有进行尾部优化.我用--optimize = tailc运行3.2.1.
有人请确切知道什么样的尾调用删除调用堆栈,哪些不？或者如何分配更多堆栈？非常感谢.
我知道Mono中的Tailcall消除
编辑:这是评论中要求的代码大纲.它是大型数据结构折叠的一部分,但失败的堆栈跟踪只有mapk和myfold.
let rec myfold f x k =
let rec mapk xs k =
match xs with
[] -> k []
| x::xs -> mapk xs (fun xs' -> myfold f x (fun x' -> (x' :: xs') |> k))
...
mapk (...) ( ... >> k)
我已经使用gcc 4.8.1和clang 3.4.190255检查了许多优化级别的汇编输出,对这种代码没有尾调用优化.
有什么特殊原因collatz_aux没有得到尾调优化？
#include <vector>
#include <cassert>
using namespace std;
vector<unsigned> concat(vector<unsigned> v, unsigned n) {
v.push_back(n);
return v;
}
vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result) {
return n == 1
? result
: n % 2 == 0
? collatz_aux(n / 2, concat(move(result), n))
: collatz_aux(3 * n + 1, concat(move(result), n));
}
vector<unsigned> collatz_vec(unsigned n) {
assert(n != 0);
return collatz_aux(n, {});
}
int main() {
return collatz_vec(10).size();
}
我正在尝试为Prolog中的第6天AdventCode编写解决方案.(http://adventofcode.com/day/6)
以前我写过一个动态创建和替换谓词的解决方案,以跟踪灯光.不出所料,它相当慢,所以我决定尝试使用更"功能"的风格来编写它; 即创建一个包含所有灯光的列表,然后操纵该列表.
我正在尝试构建初始列表,其中包含一百万个元素,每个元素都是一个术语light(X, Y, Status).我想我会从一个列表开始[light(0, 0, off)],然后为它添加新术语.为此,我查看列表的第一个元素,然后确定下一个元素应该是什么,然后预先添加.重复.
我有一个谓词next_light/2,它接受一个亮点,并确定下一个光(要预先)应该是什么.如果不再需要添加灯光,则返回done:
next_light(light(X, Y, _), NextLight) :-
X < 999,
NextX is X + 1,
NextLight = light(NextX, Y, off).
next_light(light(999, Y, _), NextLight) :-
Y < 999,
NextY is Y + 1,
NextLight = light(0, NextY, off).
next_light(light(999, 999, _), done).
然后我尝试使用以下代码构造列表:
init_lights(Lights) :-
gen_lights([light(0, 0, off)], Lights).
gen_lights(Lights, AllLights) :-
[Light|_] = Lights,
next_light(Light, NextLight),
add_light(Lights, NextLight, AllLights).
add_light(Lights, done, Lights). …