Является ли эта функция хвостовой рекурсивной? Почему это не подходит для больших списков? - PullRequest
Новая
       26

Является ли эта функция хвостовой рекурсивной? Почему это не подходит для больших списков?

1 голос
/ 08 июля 2019

Является ли эта функция хвостовой рекурсивной? 

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 элементов, пролог говорит, что он исчерпал стековую память. Как я мог это исправить?

Редактировать: я пытаюсь использовать эту функцию в качестве замены для этой функции 

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

1 Ответ

0 голосов
/ 08 июля 2019

Я не могу воспроизвести вашу проблему. С SWI-Prolog и лимитом стека в 1 ГБ я могу составить список из 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 вы используете.

...