Re: Help with lists.

student wrote: 
joonix wrote:

Greetings,

I have just started learning prolog. I come from a C/C++/Java
background and I am having a very hard time getting my head around this
style of programming.

Can some one please offer me some assistance in creating the following 

[snip]


2) A predicate no-triplicates(List1, List2) that replaces all
occurrences of any element that appears three or more times in List1
(i.e., triplicate members) with a single occurrence of that element to
generate List2. This single occurrence must occupy the position in the
list held by the first occurrence of the triplicate member in List1.
Duplicate occurrences are left unchanged. For instance, if the input
list List1 is [1, 2, 3, 2, 3, 3, 4], then the output list List2 must be
[1, 2, 3, 2, 4].

Thanks in advance,

joo.


Another possibility: 
[...]

Unless I overlooked something, all solutions that were posted were (at
least) quadratic in the length of the inputlist.

Here is a solution (works under SWI) that is potentially NlogN - but it
is up to you to discover what it takes ...

no_triplicates(In,Out) :-
        my_copy(In,In1),
        keysort(In1,In1s),
        collapse(In1s),
        skim(In1,Out).

skim([],[]).
skim([X-Y|R],Out) :-
        ( var(Y) ->
            Out = [X|Rest]
        ;
            Y = morethanonce(Z,F),
            ( var(Z) ->
                % only twice
                Out = [X|Rest]
            ;
                % more than twice, now test whether firstseen
                ( var(F) ->
                    % first occurrence
                    F = removerest,
                    Out = [X|Rest]
                ;
                    Out = Rest
                )
            )
        ),
        skim(R,Rest).


my_copy([],[]).
my_copy([X|R],[X-_|S]) :- my_copy(R,S).

collapse([]).
collapse([X|R]) :- collapse(R,X).

collapse([],_).
collapse([T2|R],T1) :-
        T1 = X1-I1,
        T2 = X2-I2,
        (X1 == X2 ->
            (var(I1) ->
                I1 = morethanonce(_,_)
            ;
                I1 = morethanonce(morethantwice,_)
            ),
            I1 = I2
        ;
            true
        ),
        collapse(R,T2).

My apologies for this impure program: I had no time to make it more
pure :-)

Cheers

Bart Demoen
.

Relevant Pages

  • Re: Help with lists.
    ... background and I am having a very hard time getting my head around this style of programming. ... occurrences of any element that appears three or more times in List1 (i.e., triplicate members) with a single occurrence of that element to generate List2. ... This single occurrence must occupy the position in the list held by the first occurrence of the triplicate member in List1. ... Duplicate occurrences are left unchanged. ...
    (comp.lang.prolog)
  • Help with lists.
    ... background and I am having a very hard time getting my head around this ... nested lists beyond the first level. ... (i.e., triplicate members) ... list held by the first occurrence of the triplicate member in List1. ...
    (comp.lang.prolog)
  • constipation
    ... I'm taking 50mg kadian 'morphine' twice a day and having a hard time ... with constipation, is oxy better or worse. ...
    (alt.support.chronic-pain)