1

I'm writing a function called subseq which checks if one list is a subsequence of another.

subseq([],[]).
subseq([],[Y|Ys]).
subseq([X|Xs],[Y|Ys]) :- X=:=Y, subseq(Xs,Ys).
subseq([X|Xs],[Y|Ys]) :- X=\=Y, subseq([X|Xs],Ys).

When I try subseq(X,[1,2]) I get:

X = [] ? ;
uncaught exception: error(instantiation_error,(=:=)/2)

Why is this happening? My guess is that [] is being operated on by =:=, but how do I check for/prevent this error?

false
  • 10,264
  • 13
  • 101
  • 209
Michael L
  • 13
  • 1
  • 3

1 Answers1

3

You use =:= and =\= in the wrong context here. Those two operators should be used when you have two expressions at hand and want to evaluate and compare them. In your test, because X is not known beforehand, Prolog couldn't evaluate X and compare with Y. More information about =:= and =\= could be found here: Prolog Operator =:=.

In your code you only need unification for atoms so one possible fix could be:

subseq([],[]).
subseq([],[_|_]).
subseq([X|Xs],[Y|Ys]) :- X=Y, subseq(Xs,Ys).
subseq([X|Xs],[Y|Ys]) :- X\=Y, subseq([X|Xs],Ys).
Community
  • 1
  • 1
pad
  • 41,040
  • 7
  • 92
  • 166
  • 1
    Many Prolog systems provide dif/2 which you could use in place of (\=)/2. I would not call this predicate subseq/2, though. – false Jun 01 '11 at 22:48