Home > Archive > Prolog > August 2005 > Help with lists.
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| joonix 2005-08-17, 4:07 am |
| 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
relationships:
1) A relation flatten( X, Y ) that holds when Y is a list structure
that contains the same elements as X, in the same order, but with no
nested lists beyond the first level. In other words, Y may contain
either atomic elements or other lists, but these may not contain any
nested lists.
Eg:
|?- flatten1( [a, b, [c,d], [[e]]], Y).
Y = [ a, b, [c, d], [e]].
no
|?- flatten1( [a,[b],[[[c]], [d,e]]], X).
X = [a,[b],[c,d,e]].
no
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.
| |
| Torkel Franzen 2005-08-17, 4:07 am |
|
"joonix" <jooonix@gmail.com> 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
s 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.
| |
| Duncan Patton 2005-08-17, 9:11 am |
| On 17 Aug 2005 10:06:34 +0200
Torkel Franzen <torkel@sm.luth.se> wrote:
This may be a little overwhelming at first, Torkel. You might=20
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. =20
Dhu
>=20
> "joonix" <jooonix@gmail.com> writes:
>=20
>=20
> flatten/2 is an old favorite, and you can easily find information
> about it on the net.
>=20
> 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.
>=20
> Disregarding the choice of programming language, what algorithm might
> we use to carry out the operation described?
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> Thus:
>=20
> delete_triplicates(L,L1):-
> delete_triplicates(L,[],L1).
>=20
> 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.
>=20
> To implement the algorithm described we further need standard
> predicates
>=20
> count(+X,+L,-N): N is the number of occurrences of X in L
> member(+X,+L): X is a member of L
>=20
> Using these, an implementation of the algorithm described is:
>=20
> delete_triplicates([],_D,[]).
>=20
> delete_triplicates([X|L],D,L1):-
> member(X,D),
> !,
> delete_triplicates(L,D,L1).
>=20
> delete_triplicates([X|L],D,[X|L1]):-
> count(X,L,N),
> N>1,
> !,
> delete_triplicates(L,[X|D],L1).
>=20
> delete_triplicates([X|L],D,[X|L1]):-
> delete_triplicates(L,D,L1).
>=20
>=20
> 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 [].
>=20
> The cuts have been introduced to make the predicate deterministic,
> that is, to ensure that a call delete_triplicates(+L,-L1) will not
> s further bindings for L1 regardless of the context in which the
> call occurs.
>=20
> 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.
>=20
--=20
???????????????????????????????????????
Can't get good help? =20
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!=20
Sun =D0hu
???????????????????????????????????????
| |
| Torkel Franzen 2005-08-17, 9:11 am |
| Duncan Patton <campbell@neotext.ca> writes:
> 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.
A good background in C or Java implies familiarity with recursion
and recursively defined data structures.
| |
| student 2005-08-19, 4:18 pm |
| 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:
reduce_triples([],[]).
reduce_triples([X|L1],[X|L2]):-
( remove(X,L1,LX), remove(X,LX,LXX) ->
removeall(X,LXX,L0), reduce_triples(L0,L2) ;
reduce_triples(L1,L2) ).
remove(X,[Y|L1],L2) :-
( X==Y -> L2=L1 ;
remove(X,L1,L0), L2=[Y|L0] ).
removeall(_,[],[]).
removeall(X,[Y|L1],L2) :-
( X==Y -> removeall(X,L1,L0), L2=L0 ;
removeall(X,L1,L0), L2=[Y|L0] ).
test :-
data(List1),
reduce_triples(List1,List2),
write(List2),nl,
fail.
test.
data([1, 2, 3, 2, 3, 3, 4]).
data([4,3,2,1,4,3,2,4,3,4]).
data([4,5,5,3,2,1,5,3,4,2,4,5,3,5,4]).
?- test.
[1, 2, 3, 2, 4]
[4, 3, 2, 1, 2]
[4, 5, 3, 2, 1, 2]
--
billh
| |
| Bart Demoen 2005-08-20, 2:56 am |
| student wrote:
> joonix wrote:
>
>
> [snip]
>
>
> 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
| |
| Torkel Franzen 2005-08-20, 2:56 am |
| Bart Demoen <bmd@cs.kuleuven.ac.be> writes:
> Unless I overlooked something, all solutions that were posted were (at
> least) quadratic in the length of the inputlist.
As noted in my comments.
> Here is a solution (works under SWI) that is potentially NlogN - but it
> is up to you to discover what it takes ...
Right, but I doubt that this could help anybody take the step from
C and Java to Prolog...
| |
| Bart Demoen 2005-08-20, 2:56 am |
| Bart Demoen wrote:
> My apologies for this impure program: I had no time to make it more
> pure :-)
Here is a purer one nevertheless - with the right complexity I think.
remove_triplets(I,O) :-
pair(I,I1,1),
sort(I1,I1s),
collect(I1s,[],Leave1),
sort(Leave1,Leave),
skim(Leave,I1,O).
skim([],_,[]).
skim([P|RP],[X-PX|RX],Out) :-
(P == PX ->
Out = [X|S],
skim(RP,RX,S)
;
skim([P|RP],RX,Out)
).
collect([],[]).
collect([X-PX|R],O) :-
eat(R,X,R1,1,N),
(N =\= 2 ->
O = [PX|O1],
collect(R1,O1)
;
R = [_-P2|_],
O = [PX,P2|O1],
collect(R1,O1)
).
eat([],_,[],N,N).
eat([A|R],X,O,I,N) :-
A = (AX-_),
(AX == X ->
I1 is I + 1,
eat(R,X,O,I1,N)
;
O = [A|R],
N = I
).
pair([],[],_).
pair([X|R],[X-I|S],I) :-
I1 is I + 1,
pair(R,S,I1).
Cheers
Bart Demoen
| |
| Markus Triska 2005-08-22, 7:02 pm |
| Bart Demoen wrote:
> collect(I1s,[],Leave1)
I suppose this should read "collect(I1s, Leave1)".
Best regards,
Markus.
| |
| Bart Demoen 2005-08-22, 7:02 pm |
| Markus Triska wrote:
> Bart Demoen wrote:
>
>
>
> I suppose this should read "collect(I1s, Leave1)".
Yes. Sorry.
And I should once more remember never to change a program once
it is pasted in the mail buffer :-(
Bart
| |
| Duncan Patton 2005-08-22, 7:02 pm |
| On Mon, 22 Aug 2005 16:11:35 +0200
Bart Demoen <bmd@cs.kuleuven.ac.be> wrote:
> Markus Triska wrote:
>=20
> Yes. Sorry.
> And I should once more remember never to change a program once
> it is pasted in the mail buffer :-(
>=20
> Bart
It's a function of editing I've noticed with people who write code is
to leave extra words in and things until the first run with a compiler.
Dhu
--=20
???????????????????????????????????????
Can't get good help? =20
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!=20
Sun =D0hu
???????????????????????????????????????
| |
| Bart Demoen 2005-08-22, 7:02 pm |
| Duncan Patton wrote:
> It's a function of editing I've noticed with people who write code is
> to leave extra words in and things until the first run with a compiler.
My sincere apologies ... I couldn't make any sense of what you wrote,
not even grammatically. Still, I would like to understand what you aim
at. Please, can you rephrase in more or less (preferably more)
understandable english the intention of your utterances ? Thanks.
| |
| Duncan Patton 2005-08-22, 9:57 pm |
| On Mon, 22 Aug 2005 22:57:41 +0200
Bart Demoen <bmd@cs.kuleuven.ac.be> wrote:
> Duncan Patton wrote:
>=20
>=20
> My sincere apologies ... I couldn't make any sense of what you wrote,
> not even grammatically. Still, I would like to understand what you aim
> at. Please, can you rephrase in more or less (preferably more)
> understandable english the intention of your utterances ? Thanks.
Ononmatopea is usually only useful as a metaphor amongst native language sp=
eakers ;)
Dhu
--=20
???????????????????????????????????????
Can't get good help? =20
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!=20
Sun =D0hu
???????????????????????????????????????
|
|
|
|
|