Prolog List Predicates

Question

I need some help with three prolog predicates for checking and manipulating lists. I'm new to prolog and any help would be much appreciated.

The three predicates are:

• double_up(+List1, -List2) is true when List2 has each element of List1 twice. The query double_up([a,b,c],X) should give X=[a,a,b,b,c,c]. The order of the elements in the output list does not matter.
• pivot(+List1, +Pivot, -Smaller, -GreaterEq) is true when Smaller is the list of numbers in List1 smaller than Pivot, and GreaterEq is the list of numbers in List1 bigger than or equal to Pivot.
• fancy_replace(+List, +Takeout,+Putin, -NewList, -Count) is true when NewList is the same list as the input List, but where each Takeout element in the list is replaced with the Putin element. Count should be the number of Takeouts that got replaced. For example, the query fancy_replace([9,10,1,9,2],9,0, X, C) should give X = [0,10,1,0,2] and C = 2. The order of the elements in the output list does not matter.

Answer 1

The simpler pattern to process lists in Prolog imposes a recursive predicate with 2 arguments, matching - conventionally - input and output data, and a base case, stopping the recursion, matching the empty list. Then

double_up([X|Xs], [X,X|Ys]) :- double_up(Xs, Ys).
double_up([], []).

This predicate it's a bit more general than what's required, because it works also in mode double_up(-List1, +List2). For instance

?- double_up(L,[1,1,2,2]).
L = [1, 2].

To restrict its mode as required, I think it's necessary to uselessly complicate the code, moving that clean loop in a service predicate, and leaving double_up just to test the arguments:

double_up(I, O) :- is_list(I), var(O), double_up_(I, O).
double_up_([X|Xs], [X,X|Ys]) :- double_up_(Xs, Ys).
double_up_([], []).

pivot/4 could be 'one-liner' in SWI-Prolog:

pivot(List1, Pivot, Smaller, GreaterEq) :-
    partition(>(Pivot), List1, Smaller, GreaterEq).

like partition, foldl from library(apply) it's an easy inplementation of the last required predicate:

fancy_replace(List, Takeout, Putin, NewList, Count) :-
    foldl(swap_n_count(Takeout, Putin), List, NewList, 0, Count).
swap_n_count(Takeout, Putin, L, N, C0, C) :-
    (   L == Takeout
    ->  N = Putin, C is C0 + 1
    ;   N = L, C = C0
    ).

Answer 2

to be honest, i hate prolog... even though it is fun and easy after you learn it

i think this is a good reference as I was having trouble understanding how prolog works couple weeks ago. what does the follow prolog codes do?

anyway.. this is the answer for your first problem; Hopefully you could solve the rest yourself :D

double([]).
double([H|[]], [H,H|[]]).
double([H|T],[H,H|T1]):- double(T, T1).

btw, this might not the only solution...but it works