Re: Help with lists.


"joonix" <jooonix@xxxxxxxxx> writes:

> 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.

flatten/2 is an old favorite, and you can easily find information
about it on the net.

no_triplicates/2 is more unusual. It's a good example of a task
where we are helped by thinking procedurally rather than declaratively
in Prolog.

Disregarding the choice of programming language, what algorithm might
we use to carry out the operation described?

One algorithm is the following: We go through the list, keeping track
of which elements are to be deleted in the remainder of the list.
For each element encountered, if it is on the deletion list, we
delete it. If not, we check how many times it occurs in the remainder
of the list. If it has at least two later occurrences, we put it on
the deletion list, and check the next element. Otherwise we just check
the next element.

We need to verify that this algorithm is correct. First, if an
occurrence of X is deleted, then X has been put on the deletion list,
and this happens only when X has been observed to have at least three
occurrences. Second, if X does have at least three occurrences, this
will be observed the first time X is encountered, and X will be
put on the deletion list, which entails that every later occurrence
will be deleted. Third, the first occurrence of any X will not be
deleted, since X cannot occur in the deletion list unless it has
already been encountered.

As is often the case, this simple and natural algorithm has quadratic
average case complexity. But the point of this example is only to
show how familiarity with programming in C or Java can carry over to
programming in Prolog, and so I set aside the topic of more efficient
algorithms.

I assume you could implement the algorithm described in C or Java.
We can implement it pretty directly in Prolog as well. The
loop described is implemented as a recursive procedure which
hands over information about the current deletion list and the current
state of the revised list being constructed to the next invocation
of the procedure.

Thus:

delete_triplicates(L,L1):-
delete_triplicates(L,[],L1).

We start with an empty deletion list, and with an unbound variable L1
which will eventually be bound to the revised list. That L1 is
initially unbound means that we have initially no information about
what the final list will look like.

To implement the algorithm described we further need standard
predicates

count(+X,+L,-N): N is the number of occurrences of X in L
member(+X,+L): X is a member of L

Using these, an implementation of the algorithm described is:

delete_triplicates([],_D,[]).

delete_triplicates([X|L],D,L1):-
member(X,D),
!,
delete_triplicates(L,D,L1).

delete_triplicates([X|L],D,[X|L1]):-
count(X,L,N),
N>1,
!,
delete_triplicates(L,[X|D],L1).

delete_triplicates([X|L],D,[X|L1]):-
delete_triplicates(L,D,L1).


Consider the call delete_triplicates([a,b,a,a,c,b,e],[],L). The
first clause does not apply, since the list is not empty. The
second clause directs us to check whether a is in the deletion list.
It isn't. So we use the third clause to compute the number, 2, of
occurrences of a in the remainder of the list. Since this is greater
than 1, we continue the procedure recursively, now with the
remainder [b,a,a,c,b,e] of the list as the list to look through,
with the deletion list as [a], and with the final result partially
specified as [a|L1], where L1 is the result of next recursive call.
As a result of that call, L will be partially specified as
[a,b|L2], where L2 is the outcome of the next recursive call,
operating on the list [a,a,c,b,e] and with no change in the deletion
list. When we reach the end of the original list, the partial result
will be "closed", by havings its tail determined as [].

The cuts have been introduced to make the predicate deterministic,
that is, to ensure that a call delete_triplicates(+L,-L1) will not
seek further bindings for L1 regardless of the context in which the
call occurs.

Suggested follow-up exercise: implement a variant of the algorithm
which doesn't count the number of occurrences of a non-triplicate
element each time it is encountered, but maintains another list
of non-triplicate elements.

.

Relevant Pages

  • Re: Theodore Adorno, a prophet of data systems design
    ... > correct algorithm proof is a rarity. ... > to hinge on how one reads the bit about actual programming experience. ... > Perhaps Mr Nilges doesn't read those threads ... >> to people as a way of asserting authority easily. ...
    (comp.programming)
  • Re: Theodore Adorno, a prophet of data systems design
    ... with the idea of "proving" an algorithm to be correct. ... Perhaps Mr Nilges doesn't read those threads ... this newsgroup isn't about "asserting authority". ... since (in the context of a programming discussion) colour only ...
    (comp.programming)
  • Re: Computer Programming Career
    ... a great image-recognition algorithm won't be ... >> evidence I offer the vast stretches of extant crap C code publically ... This problem is not limited to C, of course, but that's the language ... Arithmetic is a fundamental programming concept. ...
    (comp.programming)
  • Re: Aspiring highest-order programmer
    ... An NP algorithm, as Ian reminded us, is ... one whose execution time formula is not a polynomial. ... >>his own goddamn programming and is man enough to admit error) it was ... > reason to suspect that no such algorithm exists. ...
    (comp.programming)
  • Re: Letter to US Sen. Byron Dorgan re unpaid overtime
    ... > This is nonsense: the generallisation, and why it is bad, isn't about ... > using strlen but using an Oalgorithm when there is a trivial O ... stuff and believes it will be programming in mud hits in third ...
    (comp.programming)