Sunday, 5 August 2012

Prolog–remove duplicate list members without member predicate

 

This is completely not relevant to all my posts and a work I do. I am taking a “Prolog” class and find this language just amazing. So decided to post some of my assignments, because probably students all over a world also get similar one

My assignment is to write a program that removes duplicate list members, BUT you cannot use “member” predicate.

Lets start…

So if my list is empty there are no duplicate members for sure

rem([],[]).

The same is true if I have only one member in the list

rem([X],[X]).

Now comes the tricky part. If we recognize 2 members in the list with a same value, we will return the same list , but only with one member

rem([X,X|Tail],[X|Tail]).

And this is the start point for the program. Get the list and check it , by sending list tail to recursion

rem([X|Xs],Res):-rem(Xs,Res0),append([X],Res0,Res).

Ok, lets run it….

image

 

Well, we definitely got a correct answer, but what about incorrect answers? This is because of Prolog backtracking mechanism. After it find the correct answer it doesn’t stop and continue to check other options. So we add “red cut” to prevent backtracking

image

Now we have the correct answer 

1 comment:

  1. It works nicely on your example, but what if you have list, where the duplicates are not next to each other?

    like this -> [1,3,1] ;) Try it, you'll see..

    ReplyDelete