Predicate about a list of lists

2019-06-14 01:55发布

问题:

I'm trying to create a predicate that receives a list of lists and returns a list of lists containing all the unitary lists (lists whose length is 1) from the first list, however it is not working. This is what I created:

elimina_listas_nao_unitarias_lista_de_listas([[A]|T],N_List):-
  length([A], 1),
  N_List is [H|N_List_T],
  elimina_listas_nao_unitarias_lista_de_listas(T, N_List_T).

elimina_listas_nao_unitarias_lista_de_listas([[A]|T], N_List):-
  length([A], X),
  X > 1,
  elimina_listas_nao_unitarias_lista_de_listas(T, N_List2).

Thi is what it should do:

elimina_listas_nao_unitarias_lista_de_listas([[1,2],[1,2,3],[3]], [3])
elimina_listas_nao_unitarias_lista_de_listas([[1,2],[1,2,3],[3,4,5]], [])

It is retuning false currently everytime

回答1:

Let's take a look at your first rule. The first goal always succeeds, since you are asking if a list with a single element is of length 1. Just try it at the prompt:

   ?- length([A], 1).

true

Instead, you probably want to have a variable without the brackets in the head of the first list (e.g. [L|Ls]) and ensure that it is a list of length 1:

   ?- length(L,1).
L = [_A]

The same goes for the first list in the head of your second rule and its first goal. In your second goal you are trying to evaluate [H|N_List_T] as an arithmetic expression with is/2 such that N_List holds the value. Besides the fact that this doesn't make sense, you can try that at the prompt and see how this goal can't succeed:

   ?- N_List is [H|N_List_T].
     ERROR!!
     TYPE ERROR- string must contain a single character to be evaluated as an arithmetic expression: expected evaluable term, got [_131245|_131246]

Instead, you want to unify the two terms:

   ?- N_List = [H|N_List_T].
N_List = [H|N_List_T]

However, you can get rid of this goal entirely if you write [H|N_List_T] as the second argument in the head of the rule. Additionally, you might want the unitary list L in the head of the second list instead of the variable H. Furthermore you are missing a case, namely the first list being []. In that case the second list is empty as well, since the empty list clearly does not contain any unitary lists. Finally, I would note that it might enhance the readability of your code if you picked a somewhat simpler and more declarative name, say listas_unitarias/2. Putting all this together, you might end up with a predicate like this:

listas_unitarias([],[]).
listas_unitarias([L|Ls],[L|Ss]) :-
   length(L,1),
   listas_unitarias(Ls,Ss).
listas_unitarias([L|Ls],Ss) :-
   length(L,X),
   dif(X,1),
   listas_unitarias(Ls,Ss).

Your second example query yields the desired result

   ?- listas_unitarias([[1,2],[1,2,3],[3,4,5]],U).
U = []

For your first example query the result is slightly different:

   ?- listas_unitarias([[1,2],[1,2,3],[3]], U).
U = [[3]] ? ;
no

The only unitary list is in a list itself. That would make more sense, since the first argument might contain more than one such list. Consider the following case:

   ?- listas_unitarias([[1],[2,3],[4],[]],U).
U = [[1],[4]] ? ;
no

However, if you meant to get the unitary lists one at a time, the predicate would look slightly different:

listas_unitarias2([L|_Ls],L) :-
   length(L,1).
listas_unitarias2([_L|Ls],U) :-
   listas_unitarias2(Ls,U).

As would the results of the queries:

   ?- listas_unitarias2([[1,2],[1,2,3],[3]], U).
U = [3] ? ;
no
   ?- listas_unitarias2([[1],[2,3],[4],[]],U).
U = [1] ? ;
U = [4] ? ;
no

Especially your second example query: It would fail instead of producing the empty list as a solution:

   ?- listas_unitarias2([[1,2],[1,2,3],[3,4,5]],U).
no
   ?- listas_unitarias2([[1,2],[1,2,3],[3,4,5]],[]).
no

EDIT: As pointed out by @false in the comments the combined use of length/2 and dif/2 in the third rule doesn't terminate for [_,_|_] so the query

   ?- listas_unitarias([[1],[_,_|_],[2],[3,4]],U).
U = [[1],[2]] ? ;
U = [[1],[2]] ? ;
... 

does not terminate as well. However, it is reasonable to expect termination in this case, since a list headed by two elements certainly can't be unitary. So, instead of using length/2 you might consider describing the four cases that cover all possibilities. 1) If the first list is empty so is the second list. 2) If the head of the first list is [] it's not in the second list. 3) If the head of the first list is [A] it is in the second list. 4) If the head of the first list has at least two elements it's not in the second list.

listas_unitarias([],[]).                    % case 1)
listas_unitarias([[]|Ls],Ss) :-             % case 2)
   listas_unitarias(Ls,Ss).
listas_unitarias([[A]|Ls],[[A]|Ss]) :-      % case 3)
   listas_unitarias(Ls,Ss).
listas_unitarias([[_,_|_]|Ls],Ss) :-        % case 4)
   listas_unitarias(Ls,Ss).

With this version the above query terminates after finding the only solution:

   ?- listas_unitarias([[1],[_,_|_],[2],[3,4]],U).
U = [[1],[2]]

The other queries from above yield the same results:

   ?- listas_unitarias([[1,2],[1,2,3],[3,4,5]],U).
U = []
   ?- listas_unitarias([[1,2],[1,2,3],[3]], U).
U = [[3]]
   ?- listas_unitarias([[1],[2,3],[4],[]],S).
S = [[1],[4]]


标签: prolog