I am trying to do Regular Expression matching. I have all the functions written out, but they are not working as they should. From what I can tell, it has a problem when I try to compare a list.
For instance, "re_contains(a,a)." gives true (obviously), as does "re_contains(union(a,b),a)."
But as soon as I make it a list, it fails. "re_contains(seq(a,b), [a,b])." returns false. Append should be going through all the possible combinations to find the match, but none of these functions work correctly. This makes me thing that perhaps I am missing a base case. But I think "re_contains(X, L) :- X == L." should take care of it. I must be over looking something important here.
Here is my code:
re_contains(empty, []).
re_contains(X, L) :-
X == L.
re_contains(seq(X, Y), L) :-
append(L1, L2, L),
re_contains(X, L1),
re_contains(Y, L2).
re_contains(union(X, _), L) :-
re_contains(X, L).
re_contains(union(_, Y), L) :-
re_contains(Y, L).
re_contains(kleene(X), L) :-
append([Car|L1], L2, L),
re_contains(X, [Car|L1]),
re_contains(kleene(X), L2).
re_contains(kleene(_),[]).
append/3 will split L, and both L1 and L2 will be lists.
I would try to replace re_contains(X, L) :- X == L. with re_contains(X, [X]).
After the change, re_contains(a,a). will fail.
You are representing the sequence in different ways, and your matcher doesn't provide for both. Actually, the only cases 'working' are not sequences.