4

I'm new in prolog and I'm trying to write the predicate encode(L,L1) which counts the duplicates of elements in L ,for example:

encode([4,4,4,3,3],L).

L=[3,4,2,3].

This is what I have written:

encode(L,L1) :- encode(L,1,L1).

encode([],_,[]).      
encode([H],N,[N,H]).      
encode([H,H|T],N1,[N,H|T1]) :- M is N1+1, encode([H|T],M,[N,H|T1]).     
encode([H,Y|T],N,[N,H|T1]) :- H\=Y, encode([Y|T],T1).

The above predicate is not reversible. It only works if the first parameter is provided.

How can I write encode reversible?
For example:

encode(L,[3,4,2,3]).           
L = [4,4,4,3,3].
false
  • 10,264
  • 13
  • 101
  • 209
coder
  • 12,832
  • 5
  • 39
  • 53
  • In place of `M is N1+1` try `M #= N1 + 1`. Make sure you load the CLP(FD) module (`:- use_module(library(clpfd)).`) And in place of `\=` use `\==`. – lurker Aug 03 '16 at 14:26
  • @lurker ,I tried the above but still after making the changes ,the problem remains : encode(L,[3,4,2,3]) does not give any answer (it throws exception "Out of local stack" ). – coder Aug 03 '16 at 14:42

1 Answers1

4

I think your algorithm has a redundant counter in it. A little simplified would be:

encoded([], []).
encoded([X], [1,X]).
encoded([X,Y|T], [1,X|R]) :-
    dif(X, Y),
    encoded([Y|T], R).
encoded([X,X|T], [N,X|R]) :-
    N #> 1,
    N #= N1 + 1,
    encoded([X|T], [N1,X|R]).

Note in the last clause we need to ensure that N is greater than 1 as well.

lurker
  • 56,987
  • 9
  • 69
  • 103
  • 1
    @coder: note that even `encoded(Xs,[2,V]).` produces a perfect answer! – false Aug 03 '16 at 16:17
  • 1
    @coder: And even `encoded(Xs,[2,V,2,W]).`! Do you see the `dif` in the full answer? – false Aug 03 '16 at 16:18
  • @false ,thanks for the above notice. One thing I can't still understand is why use dif(X,Y) than X\==Y, I've tried both and both worked?? – coder Aug 03 '16 at 18:12
  • @coder: What should `V` and `W` be in the query `encoded(Xs,[2,V,2,W])`? They must be different. Thus `dif(V,W)` must be part of the answer. For, if they are identical, then it would be `[4,V]` and not `[2,V,2,W]` – false Aug 03 '16 at 18:19
  • @false: Yes but isn't the same thing if we use \== instead (I understand that X,Y must not be identical ) ??? – coder Aug 03 '16 at 18:24
  • 3
    @coder `dif(X, Y)` and `X \== Y` do not have the same behavior. For example, try this at a prompt: `X \== Y, X = 1, Y = 1`. This will **succeed**. But, `dif(X, Y), X = 1, Y = 1` will **fail** (as it should, since `X` and `Y` are not different). So `dif/2` exhibitss [*logical purity*](http://stackoverflow.com/questions/31941407/what-is-meant-by-logical-purity-in-prolog) but `\==/2` does not. – lurker Aug 03 '16 at 18:41