Re: Help with lists.

On 17 Aug 2005 10:06:34 +0200
Torkel Franzen <torkel@xxxxxxxxxx> wrote:

This may be a little overwhelming at first, Torkel. You might
start with a KISS discussion of recursion and the recursive structure
of prolog lists. I think this is one of the more significant
problems that people with experience in procedural languages
have with prolog.

Dhu

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


--
???????????????????????????????????????

Can't get good help?

Contact Fubar the Hack: fubar AT neotext.ca

Area code seven eight zero, Exchange four six six, Local zero one zero nine

Highland terms, Canadian workmanship.

All persons named herein are purely fictional victims
of the Canidian Bagle Breeder's Association.

Save the Bagle!

Sun Ðhu

???????????????????????????????????????


.

Relevant Pages

  • Re: coerce for arbitrary types
    ... the algorithm itself is essentially last-in first-out, ... via some sort of recursion? ... WaitStack <= new stack containing topnode ... As nested lists, there's only one number in a proper position. ...
    (comp.lang.lisp)
  • Re: coerce for arbitrary types
    ... algorithm that Cormen, Leiserson, and Rivest use in their DFS. ... inherently first-in first-out, like a queue, not at all stack-like ... experience, once you get over the hurdle of recursion, ... *intention* is nested lists, *not* arbitrary CONS trees. ...
    (comp.lang.lisp)
  • Re: compare element in a list prolog
    ... > for most Prolog newcomers, namely, how, starting with a blank slate, do ... > I arrive at language ... processing lists. ... For recursion, identify ...
    (comp.lang.prolog)
  • Re: Help request: recursive procedure
    ... Regardless of the implementation, you'll need a data structure for tracking the already visited fields, in order to prevent infinite recursion and retries of already checked pathes. ... The algorithm works like a flood fill, in a copy of your board. ... The first list initially contains the starting point, and all free neighbours are put into the second list. ... The processed element is removed from the list, and when the list becomes empty, both lists are swapped, and the algorithm starts the next iteration. ...
    (comp.lang.pascal.delphi.misc)
  • Re: The empty list and the end of a list
    ... I don' t know exactly what you mean by "tail ... Maybe it is a synonym for "tail recursion", ... some recursive algorithm just aren't tail recursions. ... recursive lists). ...
    (comp.lang.lisp)