CODEWITHSUNDEEP
prolog
bami77
bami77

Reputation: 51

Prolog replace every second item in list

I'm trying to learn Prolog, I'm having trouble defining the predicate:

In Prolog define a predicate substitute (L1, X, L2) which every second element of the list L1 (starting from the second element) replaces with element X.

Examples:

L1 = [a, b, c], X = 1, L2 = [a, 1, c]

L1 = [a, b, c, d], X = a, L2 = [a, a, c, a]

I tried this way:

replace( [], _, [] ) :- ! .
replace( [X|Xs], T, [Z1,Z2|Zs] ):-
  Z1 = X ,
  Z2 = T ,
  replace(Xs,T,Zs).

But it adds items to the second list, not replaces them. Thank you in advance for your help.

Upvotes: 1

Views: 107

Answers (2)

salva
salva

Reputation: 10244

You can write it as two functions that call themselves recursively in turn.

One replacing elements at odd positions, the other replacing elements at even positions:

replace_even([], _, [] ).
replace_even([H|T], R, [H|O]) :-
    replace_odd(T, R, O).

replace_odd([], _, []).
replace_odd([_|T], R, [R|O]) :-
    replace_even(T, R, O).

Upvotes: 0

Nicholas Carey
Nicholas Carey

Reputation: 74277

Your problem is that you are pulling items off the list 1 at a time. To replace every other item, you can do it a couple of ways:

  • Pull items off 2 at a time

    Try this to replace the even number list elements (where the 1st element in the list is item number 1.

    You have the special case of the empty list:

    replace( [] , _ , [] ) .

    And the special case of a list of length 1:

    replace( [X] , _ , [X] ) .

    And then the general case (lists of length > 1):

    replace( [X,_|Xs] , R , [X,R|Ys] ) :- replace(Xs, R, Ys).

    Putting it all together, we get:

    replace( []       , _ , []       ) .
replace( [X]      , _ , [X]      ) .
replace( [X,_|Xs] , R , [X,R|Ys] ) :- replace(Xs, R, Ys).

  • Track State As You Go

    This isn't much more difficult. And it opens the possibility of making things more general. To do this we use a helper predicate. Ultimately, it's not a lot different.

    First, our replace/3 is just a wrapper around invoking the helper predicate, to which we pass two additional bits of state:

    • the current index value (1), and
    • the modulus we'll use to determine which elements get replaced
    replace( Xs, R, Ys ) :- replace(Xs, R, 1, 2, Ys).

    Here's the helper predicated replace/5:

    replace( []     , _ , _ , _ , []     ) .
replace( [X|Xs] , R , N , M , [Y|Ys] ) :-
  try_swap(X,R,N,M,Y),
  N1 is N+1,
  replace(Xs, R, N1, M, Ys ).

try_swap( _ , R , N , M , R ) :- 0 is N mod M, !.
try_swap( X , _ , _ , _ , X ) .

    And putting it all together:

    replace( Xs, R, Ys ) :- replace(Xs, R, 1, 2, Ys).

replace( []     , _ , _ , _ , []     ) .
replace( [X|Xs] , R , N , M , [Y|Ys] ) :-
  try_swap(X,R,N,M,Y),
  N1 is N+1,
  replace(Xs, R, N1, M, Ys ).

try_swap( _ , R , N , M , R ) :- 0 is N mod M, !.
try_swap( X , _ , _ , _ , X ) .

Upvotes: 0

Related Questions