list length, inserting element

4

votes

I'm trying to write a program in Prolog, which will insert an element into a certain position, so e.g.

?- ins(a, [1,2,3,4,5], 3, X).
X = [1,2,a,3,4,5].

I have the following code:

ins(X,[H|T],P,OUT) :-
   length([T3],P),
   concatenate(X,[H],T),
   ins(...).

The problem is that it is inserting element X in given index from back (I even know where the problem is -> the length([T3],P) which is obviously the length of the list from back not from head) . I was trying to remember how much elements did I cut off and insert X when "number of cut off elements" = P, but I can't really write that in Prolog. Any ideas?

listprolog

3

votes

% ins(Val,List,Pos,Res)

ins(Val,[H|List],Pos,[H|Res]):- Pos > 1, !, 
                                Pos1 is Pos - 1, ins(Val,List,Pos1,Res). 
ins(Val, List, 1, [Val|List]).

The predicate fails if Pos = 0 or Pos > length(List) + 1

3

votes

Let's state what you want here. For example you could say: "I want to split my input List after Position - 1 elements so that I can insert a new element there".

A direct traduction with append/3 (DCG would be better btw):

ins(Element, List, Position, Result) :-
    PrefixLength is Position - 1,
    length(Prefix, PrefixLength),
    append(Prefix, Suffix, List),
    append(Prefix, [Element], Temp),
    append(Temp, Suffix, Result).

Or you could say: "I want to go through the elements of my List Position - 1 times without touching anything and then insert Element and then not touch anything again".

This time the direct traduction would be:

ins2(Element, List, 1, [Element|List]).
ins2(Element, [Head|Tail], Position, [Head|Result]) :-
    Position > 1,
    NewPosition is Position - 1,
    ins2(Element, Tail, NewPosition, Result).

you could too state that: "My input List is a list equal to my Result one except it hasn't my Element as Positionth element." and realize that if you use swi-prolog, a predicate solves this instantly:

ins3(Element, List, Position, Result) :-
    nth1(Position, Result, Element, List).

Bottom line is: state what the problem is clearly and the solution should appear in simple terms.

2

votes

TL;DR: To insert item E at position I1 into list Es0, we do not need to write recursive code.

Instead, we can delegate the work (and the worries about getting it right, too!) to versatile auxiliary predicates, all of which are part of the Prolog prologue. To define ins_/4 we write:

ins_(E, Es0, I1, Es) :-
    maplist(any_thing, Es, [_|Es0]),
    append(Prefix, Suffix, Es0),
    length([_|Prefix], I1),
    append(Prefix, [E|Suffix], Es).

any_thing(_, _).                        % auxiliary predicate (used above)

Note that maplist(any_thing, Es, [_|Es0]) is equivalent to same_length(Es, [_|Es0]).

Sample queries^1,2,3 using GNU Prolog version 1.4.4 (64-bit):

?- ins_(X, [a,b,c,d,e], N1, Xs).            
  N1 = 1, Xs = [X,a,b,c,d,e] 
; N1 = 2, Xs = [a,X,b,c,d,e]
; N1 = 3, Xs = [a,b,X,c,d,e]
; N1 = 4, Xs = [a,b,c,X,d,e]
; N1 = 5, Xs = [a,b,c,d,X,e]
; N1 = 6, Xs = [a,b,c,d,e,X]
; false.

?- ins_(X, [a,b,c,d,e], 3, Xs).
  Xs = [a,b,X,c,d,e]
; false.

?- ins_(X, Xs0, 3, [a,b,c,d,e]).            
  X = c, Xs0 = [a,b,d,e]
; false.

Let's not forget about the most general query!

?- ins(X, Es0, I1, Es).
  Es0 = [], I1 = 1, Es = [X]
; 
  Es0 = [A], I1 = 1, Es = [X,A]
; Es0 = [A], I1 = 2, Es = [A,X]
; 
  Es0 = [A,B], I1 = 1, Es = [X,A,B]
; Es0 = [A,B], I1 = 2, Es = [A,X,B]
; Es0 = [A,B], I1 = 3, Es = [A,B,X]
; 
  Es0 = [A,B,C], I1 = 1, Es = [X,A,B,C]
; Es0 = [A,B,C], I1 = 2, Es = [A,X,B,C]
; Es0 = [A,B,C], I1 = 3, Es = [A,B,X,C]
; Es0 = [A,B,C], I1 = 4, Es = [A,B,C,X]
; 
  Es0 = [A,B,C,D], I1 = 1, Es = [X,A,B,C,D]
; ...

Fair enumeration of all solutions, OK!

EDIT: I repeated the most general query with ins3/4 as defined by @m09 in his answer on SWI-Prolog 7.3.11 and SICStus Prolog 4.3.2 (both feature the library predicate nth1/4). I was surprised to see the underlying implementations of nth1/4 exhibit different procedural semantics (w.r.t. "fair enumeration"). See for yourself!

% SICStus Prolog 4.3.2                    % SWI Prolog 7.3.11
%                                         % 
?- ins3(X, Es0, I1, Es).                  %   ?- ins3(X, Es0, I1, Es).
  I1 = 1, Es0 = [], Es = [X]              %     I1 = 1, Es  = [X|Es0]
;                                         %   ; I1 = 2, Es0 = [_A|_Z], 
  I1 = 1, Es0 = [_A], Es = [X,_A]         %             Es  = [_A,X|_Z]
; I1 = 2, Es0 = [_A], Es = [_A,X]         %   ; I1 = 3, Es0 = [_A,_B|_Z],
;                                         %             Es  = [_A,_B,X|_Z] 
  I1 = 1, Es0 = [_A,_B], Es = [X,_A,_B]   %   ; I1 = 4, Es0 = [_A,_B,_C|_Z],
; I1 = 2, Es0 = [_A,_B], Es = [_A,X,_B]   %             Es  = [_A,_B,_C,X|_Z],
; I1 = 3, Es0 = [_A,_B], Es = [_A,_B,X]   %   ; I1 = 5, Es0 = [_A,_B,_C,_D|_Z],
;                                         %             Es  = [_A,_B,_C,_D,X|_Z]
...                                       %   ...

^{Footnote 1: All sample queries shown above terminate universally.}
^{Footnote 2: The answers given by the GNU Prolog toplevel have been pretty-printed a little.}
^{Footnote 3: The code presented above is used as-is, no additional library predicates are required.}

0

votes

ins(Element,List,Nth,Result) :-
    length([_|L0],Nth),
    append(L0,[_|R],List),
    append(L0,[Element|R],Result).

list length, inserting element

4 Answers