时间戳

首页 > 解决方案 > 这个函数是尾递归的吗？为什么大列表会失败？

prolog - 这个函数是尾递归的吗？为什么大列表会失败？

问题描述

这个函数是尾递归的吗？

incNth(0, [H1|T], [H2|T]) :-
  H2 is H1 + 1.
incNth(N, [H|T1], [H|T2]) :-
  N > 0, N2 is N - 1,
  incNth(N2, T1, T2).

对于包含 500,000 个元素的列表，prolog 表示堆栈内存不足。我该如何解决这个问题？

编辑：我正在尝试使用此功能作为此功能的替代品

insert(Ind,List,Val,NList) :-
    nth0(Ind,List,_,R),
    nth0(Ind,NList,Val,R)

标签： prologtail-recursion

解决方案

我无法重现您的问题。使用 SWI-Prolog 和 1GB 的堆栈限制，我可以列出 10 000 000 个元素（即 1e7），并成功地将谓词应用于它。

?- N = 10 000 000, length(L, N), maplist(=(0), L), incNth(N-1, L, R).
N = 10000000,
L = [0, 0, 0, 0, 0, 0, 0, 0, 0|...],
R = [0, 0, 0, 0, 0, 0, 0, 0, 0|...] ;
false.

这是 2 * 10 倍于您的列表。

如果我尝试制作更长的列表，这就是我用完堆栈空间的时候。这已经抛出：

?- N = 50 000 000, length(L, N).
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 1Kb, global: 4Kb, trail: 2Kb
ERROR:   Stack depth: 11, last-call: 18%, Choice points: 3
ERROR:   In:
ERROR:     [11] system:'$length'(_1226, 50000000)
ERROR:     [9] system:'<meta-call>'(<compound (:)/2>)
ERROR:     [8] '$tabling':'$wfs_call'(<compound (:)/2>, <compound (:)/2>)
ERROR:     [7] '$toplevel':toplevel_call(<compound (:)/2>, <compound (:)/2>)
ERROR:     [5] '$toplevel':'$execute_goal2'(<compound (:)/2>, [length:3])
ERROR: 
ERROR: Use the --stack_limit=size[KMG] command line option or
ERROR: ?- set_prolog_flag(stack_limit, 2_147_483_648). to double the limit.

请说明您如何运行程序以及您看到的错误。还请告诉我们您正在使用什么 Prolog 实现。

推荐阅读