Parsing a list of lists in Prolog

Question

I'm new to Prolog. Consider the following example:

MainList =  [["A","a","0"],["A","b","0"],["B","a","0"],["B","b","0"],["A","a","1"],["B","b","1"],["C","c","1"],["C","a","0"]]
SubList = ["A","b","-']

The format of MainList: in the first index it should be the big letter, second index should be small letter and third index should be number. MainList can contain other formats (and lengths) but I choose this format because it is easier to explain. I just want to explain that there index of each sublists are divided into categories - first element of each list belongs to category1, second element to category2 and so on. The "-" symbol means we does know about the bond of that element with the other elements.

The relation I would like to create should go through the MainList and remove all of the sublists that does not follow SubList. For the example above, it should return:

Output =  [["A","b","0"],["B","a","0"],["C","c","1"],["C","a","0"]]

Explanation: "A" is working together with "b" so every sublists that contains one of those elements, should be checked. if they both exists then it's ok (without duplicates). Otherwise if only one of them exists, it is not ok and we should not insert it into the Output list.

Another example (MainList is a bit different than the one before):

MainList =  [["A","a","0"],["A","b","0"],["B","a","0"],["B","b","0"],["A","b","1"],["B","b","1"],["C","c","1"],["C","a","0"]]
SubList = ["C","a","0"]
Output = [["A","b","1"],["B","b","1"],["C","a","0"]]

I do understand the algorithm - we should go through each sublist of the MainList and check if the connection of the input-sublist is working, if so, we will insert it into the Output list. The problem is, I don't understand how to implement it right. What if the sublist contains more than 2 connections (as was shown in the second example)? How should I treat differently to the sublist?

EDIT: I'll try to explain a bit more. The place of each element is important. Each place represents a different category. For example, the first place might represent the big letters, the second place represents the small letters and the third place represents numbers (there could be more categories). We get a sublist which represents a bond between two or more elements. For example we have a bond between "A" and "b": ["A","b","-"]. We should iterate through the sublists of MainList and check if each one of those sublists contains one of those elements ("A" and "b"). If it does, we should check if the bond is correct. For example if we have a sublist that has A (in the first index of course), then we should go to the second index and check if "b" is there. if it is not there, we should not insert it into the Output list, Otherwise we will insert. For example we have a bond ["A","b","-"] and we got into a sublists of MainList which looks as following: ["A","a","0"] or ["B","b","2"]. We will not inert those lists into Output. But if we got to sublists like: ["A","b","1"] and ["A","b","2"] and ["B","a","1"] we will insert those lists into Output.

...remove all of the sublists that does not follow SubList. I'm not clear on what this means. In your first example, ["B","a","0"] follows ["A","b","0"] which matches the Sublist, ["A","b",_]. In your second example, the output does not include ["A","a","0"] which does not follow the sublist, ["C","a","0"]. — lurker
@lurker Thanks for the reply. By follow I meant that there if the sublists is ["A","b","-"] then we have a bond between A and b. ["B","a","0"] does not contain A or b then we will insert it into Output. But ["A","a","0"] contains A but not b, so this bond does not true. I'll try to edit it. — vesii
Ok thanks. Also be careful with _. It's not at all the same as "-". _ is an anonymous variable in Prolog. It will unify successfully with any term. — lurker
@lurker Yes, you are right, it is my mistake. Can you see what I'm trying to achieve now? :) — vesii

Koralp Catalsakal Koralp Catalsakal · Accepted Answer · 2019-01-23T17:21:31

I wrote a code that satisfies the output conditions for the examples you have given, but did not try other cases or consider the efficiency of the code, so you can maybe improve upon it. Here is the code :

subList(List,SubL,Out):-
    (member("-",SubL),
     select("-",SubL,SubRem)
    ;
    \+ member("-",SubL),
    SubRem = SubL),
    findall(L,((member(L,List),checkEq(SubRem,L));
           (member(L,List),checkNeq(SubRem,L))),Out).

checkEq([],_).
checkEq([S|Rest],[E|List]):-
    S == E,
    checkEq(Rest,List).

checkNeq([],_).
checkNeq([S|Rest],List) :-
    \+ member(S,List),
    checkNeq(Rest,List).

Explanation: What I did is that, first I removed the "-" character from the subarray(if it exists) in order to make the computations easier. Then, I either check the condition that each element in the SubList is in order with the elements of the selected sublist of the MainList. If this fails, I then check if none of the elements of SubList is contained in the selected sublist. If both checks fail, I move to the next sublist. Using findall/3 predicate, I find all combinations that satisfy either of these conditions and group them in the list Out

EDIT: Add the additional clause for the checkEq predicate :

checkEq([S|Rest],[E|List]):-
    S \= E,
    member(S,List),
    checkEq([S|Rest],List).

So the final version is :

checkEq([],_).
checkEq([S|Rest],[E|List]):-
    S == E,
    checkEq(Rest,List).

checkEq([S|Rest],[E|List]):-
    S \= E,
    member(S,List),
    checkEq([S|Rest],List).

Parsing a list of lists in Prolog

1 Answers