1.08 (**) Eliminate consecutive duplicates of list elements. If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed. Example: ?- compress([a,a,a,
The Quiet Center
many special purpose languages and systems:
* mindmaps
* make/build systems
* dataflow diagrams
It is the last analogy that I wish to apply to a novice Prolog
program. I've never mastered Prolog, but I'm hoping to make it through
all 99 prolog problems and then move on to advanced topics like DCGs,
and object-oriented Prolog, etc.
But anyway, the first problem that I found difficult was problem
number 8. It tooks me two days and a bit of help from "RLa" in
irc://irc.freenode.net/##prolog to get it working:
% http://sites.google.com/site/prologsite/prolog-problems/1
% Problem 1.08 - compress consecutive duplicates into a single
% list element
compress([], []).
compress([X,Y], [X,Y]) :- X \= Y.
compress([X,Y], [X]) :- X = Y.
% problems writing other clauses (thanks RLa)
compress([X,Y|Z], [X|Z1]) :- X \= Y, compress([Y|Z], Z1).
compress([X,Y|Z], Z1) :- X = Y, compress([Y|Z], Z1).
# why was it so hard?
The reason it was so hard is that Prolog does not force you to
partition the flow of the input list based on discrete cases. Even
though there is a definite dataflow to this program, it is structured
as clause head and body not inflow to outflow. Let me explain.
For example, here is how a dataflow program executes:
1 -> 2 -> 3 -> ... -> n-1 -> n
By contrast if we enumerate the order in which the Prolog clauses
executes
we would have:
dataflow(1, n) :- 2, 3, ... n-1.
Where the numbers represent data processing steps.
So what we see is the clause head is "alpha" and "omega" of a data
flow. While a dataflow diagram expresses the linear processing flow
in a linear way, some of the linear processing is done by pattern
matching in the head.
Let's look at the first clause in the program:
compress([], []).
If this were a dataflow program, it would look like:
INLIST -> LENGTH(INLIST) = 0? -> OUTLIST = []
The pattern matching nature of Prolog makes the expression of the
dataflow compact. However, it does not put it in sequential
order.
Let's take a look at another couple of clauses:
compress([X,Y], [X,Y]) :- X \= Y.
compress([X,Y], [X]) :- X = Y.
INLIST -> LENGTH(INLIST) 0? -> OUTLIST = []
-> LENGTH(INLIST) 2?
-> (= car cadr)? -> OUTLIST = car(INLIST)
-> else -> OUTLIST = INLIST
Jan Burse
> For example, here is how a dataflow program executes:
>
> 1 -> 2 -> 3 -> ... -> n-1 -> n
>
Under the hood, the resolution step of Prolog, does exactly
do this. But it is non-deterministic...
Bye
bart demoen
> % Problem 1.08 - compress consecutive duplicates into a single
> % list element
I know you didn't ask for a solution - you have found it yourself.
But I cannot resist the temptation to post my favourite version of
compress:
compress(In,Out) :- compress(In,[_|In],[_|Out]).
compress([],[A|_],[A]).
compress([A|R],[B|S],Out) :- (A == B -> compress(R,S,Out) ; Out = [B|
Out1], compress(R,S,Out1)).
Cheers
Bart Demoen