list length, inserting element
Solution 1
% 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
Solution 2
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 Position
th 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.
Solution 3
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 queries1,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.
Johnzzz
Updated on June 04, 2022Comments
-
Johnzzz almost 2 years
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 -> thelength([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 insertX
when "number of cut off elements" =P
, but I can't really write that in Prolog. Any ideas? -
Johnzzz about 12 yearspos>1, newPos is P -1, wuaa that's what i was looking for :) thx a lot
-
Tobias Liefke over 8 yearsWhile this code may answer the question, it would be better to explain how it solves the problem and why to use it. Code-only answers are not useful in the long run.
-
repeat over 8 yearsThe query
?- ins_(a,[1,2,3,4,5],3,[1,2,a,3,4,5]).
fails, it should succeed. OTOH the query?- ins_(a,[1,2,3,4,5],3,[1,2,a,4,5]).
succeeds, it should fail. To fix the bug you need to delete exactly 4 characters:)