Equating a Sublist to Another Sublist for CYK tabl

问题:

I'm currently working on a Prolog program that will generate a CYK parse table after being given a set of productions. However, I am having troubles checking two rows to see if they are equivalent. Here's what I have so far:

answer(X,X).

%Checks to see if it is equivalent

equal(X,Y) :- sort(X,X1), sort(Y,Y1), X1 == Y1.

%find the length of the lists

total_length([],0).
total_length([_|Xs],L) :- total_length(Xs,M), L is M+1.

%storing length of lists and possible use of a decrement here to decrement the length...but don't understand how 

storing(M,N) :- total_length(L,L_length), total_length(N,N_length), L_length is N_length, answer(L_length,N_length).

%Check for row equivalence...again, trying to find a way to decrement for the recursion, but unsure how to do it

sublist_check(Ra,Rb) :- storing(Ra,Rb), nth0(X,Ra,R1), nth0(Y,Rb,R2), equal(R1,R2), sublist_check(Ra,Rb).

Let's say an input is:

sublist_check([["A"],[],[]], [[],["A"],[]]). -->
false.

sublist_check([["A"],["B","C"],["B","C"]],[["A"],["C","B"],["C","B"]]). -->
true.

I think my issue is that I need to find a way to create a variable equivalent to the max length of the list and decrement it every time, but I run into the error of setting the initial length of sublist_check back to its original number.

Any input/feedback would be brilliant, thanks so much!

回答1:

If i've understood properly your problem, you want to check if the two lists in the same position in the two list of lists, have the same elements. You can do it in this way:

check([],_).
check([H|T],L):-
    member(H,L),
    check(T,L).

sublist_check([],[]).
sublist_check([H1|T1],[H2|T2]):-
    check(H1,H2),
    sublist_check(T1,T2).

?- sublist_check([["A"],["B","C"],["B","C"]],[["A"],["C","B"],["C","B"]]).
true

?- sublist_check([["A"],[],[]], [[],["A"],[]]).
false

回答2:

This is a shorter coding of damianodamiano answer (+1)

check1(S,L) :- maplist(member_(L), S).
sublist_check1(A,B) :- maplist(check1, A,B).

member_(L,H) :- member(H,L).

Using library(yall), it's more appealing:

check2(S,L) :- maplist({L}/[H]>>member(H,L), S).
sublist_check2(A,B) :- maplist(check2, A,B).

library(yall) it's not alone... After

?- pack_install(lambda).

you can

:- use_module(library(lambda)).
check3(S,L) :- maplist(\H^member(H,L),S).
sublist_check3(A,B) :- maplist(check3, A,B).