вставка целого числа в отсортированный список

Question

Итак, моя проблема в том, что у меня есть предикат insere_ordenado (El, Lst1, Lst2), в котором El - случайное целое число, Lst1 - список, а Lst2 - результирующий список добавления El в Lst1.

Дело в том, что я сделал это рекурсивно, но теперь я должен сделать это итеративно, и проблема в том, что когда я хочу добавить число, которое больше или равно наибольшему числу в списке, оно ничего не добавляет.

Пример:

?- insere_ordenado_ite(2,[1,2,3,6,9],L2).
L2 = [1, 2, 2, 3, 6, 9].

?- insere_ordenado_ite(5,[1,2,3,6,9],L2).
L2 = [1, 2, 3, 5, 6, 9].

?- insere_ordenado_ite(0,[1,2,3,6,9],L2).
L2 = [0, 1, 2, 3, 6, 9].

?- insere_ordenado_ite(9,[1,2,3,6,9],L2).
L2 = [1, 2, 3, 6, 9] .

?- insere_ordenado_ite(10,[1,2,3,6,9],L2).
L2 = [1, 2, 3, 6, 9] .

Как вы можете видеть в примере, я хочу добавить 9 или 10, в конце следует добавить 9 или 10 (в зависимости от примера).

Программа:

insere_ordenado_ite(El,L1,L2) :-  insere_ordenado_ite(El,L1,L2,[]).

insere_ordenado_ite(El,[],L2,L2).

insere_ordenado_ite(El,[P|R],L2,AC) :- El >= P,
                                       append(AC,[P],NAC),
                                       insere_ordenado_ite(El,R,L2,NAC).

insere_ordenado_ite(El,[P|R],L2,AC) :- El < P,
                                       append(AC,[El,P],NAC),
                                       append(NAC,R,NNAC),
                                       insere_ordenado_ite(El,[],L2,NNAC).

Я думаю, что проблема в том, что чего-то не хватает в состоянии остановки, но я не уверен, что это такое или как именно это сделать, честно говоря, любая помощь будет оценены.

Answer 1

Как насчет этого, который у меня есть под рукой?

Это настолько итеративно, насколько это возможно, ничего не происходит после insert_help/3 вызова. Хвост difflist ограничен допустимым списком в конце концов, и поскольку переменные действительно глобальные, этот факт сразу виден любому, кто разделяет переменную, в данном случае insert/3.

insert(P,List,T) :-
   DiffList=[-1|T]-T, % -1 is a guard, smaller than anything, removed later
   insert_help(P,List,DiffList).   

insert_help(P,[Px|R],H-T) :-
    P>Px,!,
    format("go right at ~q into ~q, difflist: ~q\n",[P,[Px|R],H-T]),
    T=[Px|TT],
    insert_help(P,R,H-TT).

insert_help(P,[P|R],H-T) :-
    !,
    format("~q exists in ~q, difflist: ~q\n",[P,[P|R],H-T]),
    T=[P|R].

insert_help(P,[Px|R],H-T) :-
    P<Px,!,
    format("insert-before at ~q into ~q, difflist: ~q\n",[P,[Px|R],H-T]),
    T=[P,Px|R].

insert_help(P,[],H-T) :-
    !,
    format("insert ~q at end, difflist: ~q\n",[P,H-T]),
    T=[P].

:-begin_tests(inserting).

test(1) :- insert(10,[],R),R=[10].
test(2) :- insert(11,[2,3,5,7],R),R=[2,3,5,7,11].
test(3) :- insert(2,[3,5,7,11],R),R=[2,3,5,7,11].
test(4) :- insert(3,[2,3,5,7,11],R),R=[2,3,5,7,11].
test(5) :- insert(3,[2,5,7,11],R),R=[2,3,5,7,11].
test(6) :- insert(7,[2,3,5,11],R),R=[2,3,5,7,11].
test(7) :- insert(2,[],R),R=[2].

:-end_tests(inserting).

rt :- run_tests(inserting).

Приложение: Решение это с append/{2,3}

Если у вас есть append/3 (и append/2), вы можете просто сделать:

insert_with_append(El,List,Out) :-
   search(El,List,0,Result),
   ((Result >= 0)                       % -1 means entry exists
    ->
       (length(Front,Result),           % create list of fresh variables of length Result
        append(Front,Back,List),        % rip list apart into Front, Back
        append([Front,[El],Back],Out))  % build result
    ;
       Out = List % already exists in list
    ).

% search/4 looks for the insert position, counting the number of 
% items in List that come before Element, and setting CounterOut
% to that value, once known. CounterOut is set to -1 if Element
% is already in the list.

% search(Element,List,CounterCur,CounterOut)

search(_,[],Counter,Counter) :- !.

search(E,[L|Ls],CounterCur,CounterOut) :-
   L<E,!,
   succ(CounterCur,CounterNext),
   search(E,Ls,CounterNext,CounterOut).

search(E,[L|_],CounterCur,CounterCur) :-
   E<L,!.

search(E,[E|_],_,-1). 


:-begin_tests(insert_with_append).

test(1) :- insert_with_append(10,[],R),R=[10].
test(2) :- insert_with_append(11,[2,3,5,7],R),R=[2,3,5,7,11].
test(3) :- insert_with_append(2,[3,5,7,11],R),R=[2,3,5,7,11].
test(4) :- insert_with_append(3,[2,3,5,7,11],R),R=[2,3,5,7,11].
test(5) :- insert_with_append(3,[2,5,7,11],R),R=[2,3,5,7,11].
test(6) :- insert_with_append(7,[2,3,5,11],R),R=[2,3,5,7,11].
test(7) :- insert_with_append(2,[],R),R=[2].

:-end_tests(insert_with_append).

rt :- run_tests(insert_with_append).