CODEWITHSUNDEEP
prolog
pkoch
pkoch

Reputation: 2722

How can I make this more logic-y?

I was trying to solve the following problem from chapter 6's exercises on LPN!:

Write a predicate set(InList,OutList) which takes as input an arbitrary list, and returns a list in which each element of the input list appears only once. For example, the query

set([2,2,foo,1,foo, [],[]],X).

should yield the result

X = [2,foo,1,[]].

I got to this:

set_([], [], []).
set_([H|Bag], [H|Set], Dups):-
  set_(Bag, Set, Dups),
  \+ member(H, Set),
  \+ member(H, Dups).
set_([H|Bag], Set, [H|Dups]):-
  set_(Bag, Set, Dups),
  member(H, Set).

set(Bag, Set, Rest):-
    reverse(BagR, Bag),
    set_(BagR, SetR, RestR),
    reverse(SetR, Set),
    reverse(RestR, Rest).

set(Bag, Set):- set(Bag, Set, _).

But I'm pretty unimpressed by needing those 3 reverse/2. Can anybody help me figure out a more elegant solution to this?

I tried to do a right-recursive solution first, but it would get stuck trying to prove the problem could "go on". For example, if I called set_([1,2,1], L, R), it would get stuck proving set(_, [1,2|_], [1|_]).. If you have feedback on how to avoid that, let me know!

Edit 1: I ended up using foldl/4:

pushForward(X, [Set0, Rest], [Set, Rest]):-
  \+ member(X, Set0),
  append([Set0, [X]], Set).
pushForward(X, [Set, Rest0], [Set, Rest]):-
  member(X, Set),
  append([Rest0, [X]], Rest).

set(Bag, Set, Rest):- foldl(pushForward, Bag, [[],[]], [Set, Rest]).

set(Bag, Set):- set(Bag, Set, _).

However, this doesn't really get to the heart of the problem. I wished I was able to specify the relationships of a model, and ask for "what fits in these holes". This solution does the opposite -- it takes some values and munges them until we have nothing else to do -- and that should be Prolog's job, not mine. ;)

Upvotes: 2

Views: 130

Answers (2)

false
false

Reputation: 10102

The name is not ideal. Using library(reif):

list_nub([], []).
list_nub([E|Es], [E|Gs]) :-
   tfilter(dif(E), Es, Fs),
   list_nub(Fs, Gs).

?- Xs = [_,_,_], Ys = [_,_], list_nub(Xs, Ys).
   Xs = [_A,_A,_B], Ys = [_A,_B], dif(_A,_B)
;  Xs = [_A,_B,_A], Ys = [_A,_B], dif(_A,_B)
;  Xs = [_A,_B,_B], Ys = [_A,_B], dif(_A,_B)
;  false.
?- Xs = [_,_,_], Ys = [_], list_nub(Xs, Ys).
   Xs = [_A,_A,_A], Ys = [_A]
;  false.
?- Xs = [_,_,_], Ys = [_,_,_], list_nub(Xs, Ys).
   Xs = [_A,_B,_C], Ys = [_A,_B,_C], dif(_A,_B), dif(_A,_C), dif(_B,_C).
?- dif(A,B), Xs = [A|_], Ys = [B|_], list_nub(Xs, Ys).
   false.

Upvotes: 3

CapelliC
CapelliC

Reputation: 60014

In Prolog it's always worth to purse the simplest solution, so

  • copy elements from InList to an Accumulator, only if they aren't already present, using a simple recursion.
  • reverse the resulting Accumulator to OutList.

As a micro optimization, you could use memberchk/2 instead of member/2 to check is the element should be discarded.

Since you're learning the language, I will not show the complete solution.

Upvotes: 2

Related Questions