Prolog: ¿cómo comprobar si una lista incluye ciertos elementos?

Question

Estoy probando Prolog por primera vez y estoy teniendo algunas dificultades para usar las listas.

Di que tengo una lista de elementos. Quiero comprobar que la lista tiene los siguientes elementos:

Todos: A1, A2, A3, A4, A5

Uno de: B1, B2, B3, B4

Dos de: C1 , C2, C3, C4, C5, C6

Por ejemplo, [A1, A2, B2, C1, A3, A4, C4, A5] cumple los requisitos y [A2, A1, C1, B1, A3, A4 ] no.

¿Qué debo hacer para escribir algo que devuelve Sí/Verdad si una lista cumple con los requisitos y No/Falso de lo contrario? Del mismo modo, ¿qué hay de escribir algo que devuelva los valores que faltan de la lista necesaria para cumplir con los requisitos?

Answer 1

¡Has hecho muchas preguntas! Permítanme comenzar con algunos predicados que resuelven la mayoría de sus requisitos.

En primer lugar vamos a abordar el caso de comprobar que todas las entradas de una lista están también en la otra lista:

subset([ ],_). 
subset([H|T],List) :- 
    member(H,List), 
    subset(T,List). 

Este sencillo recursividad hace uso de lo familiar/2 predicado miembro verificar cada entrada en la lista especificada por el primer argumento de subconjunto/2 también se encuentra en la lista especificada por el segundo argumento. [Por simplicidad, he supuesto que las entradas de esta lista son distintas. Sería necesaria una versión más elaborada si quisiéramos verificar que varias instancias de una entrada de la primera lista coinciden al menos con tantas instancias en la segunda lista.]

Bien, qué tal un cheque que (al menos) uno de una primera lista pertenece también a la segunda lista? Obviamente, este es un predicado diferente al anterior. En lugar de todos los artículos en la primera lista, el objetivo debe cumplirse si existe cualquier artículo en la primera lista que pertenece a la segunda lista.

intersects([H|_],List) :- 
    member(H,List), 
    !. 
intersects([_|T],List) :- 
    intersects(T,List). 

Esta recursión falla si alcanza una lista vacía para el primer argumento, pero tiene éxito si en algún momento antes de que un miembro de la primera lista se encontró que pertenece a la segunda lista. [Este predicado funcionaría bien incluso si ocurrieran múltiples instancias de un elemento en cualquiera de las listas. Sin embargo, necesitaríamos refinar la lógica si quisiéramos marcar exactamente un elemento de la primera lista pertenece a la segunda lista, y eso implicaría preocuparse sobre si las instancias múltiples son consistentes o contrarias al recuento exacto de uno.]

¿Qué sucede si queremos generalizar esta comprobación, para verificar (al menos) N elementos de la primera lista están en la segunda? El predicado resultante será necesario un tercer argumento:

intersectsAtLeast(_,_,N) :- N <= 0, !. 
intersectsAtLeast([H|T],L,N) :- 
    member(H,L), 
    !, 
    M is N-1, 
    intersectsAtLeast(T,L,M). 
intersectsAtLeast([_|T],L,N) :- 
    intersectsAtLeast(T,L,N). 

Esta recursión trabaja a través de la lista, disminuyendo el tercer argumento en uno cada vez que un elemento de la primera lista resulta ser en la segunda lista, así, y tener éxito una vez que el recuento se reduce a 0 (o menos). [De nuevo, el código aquí necesita más trabajo si las listas pueden tener repeticiones.]

Finalmente, pregunta por escribir algo que "devuelve los valores faltantes" para cumplir con los requisitos. Esto no está bien definido en el caso de verificar uno o más elementos en ambas listas, ya que un "valor perdido" podría ser uno cualquiera de una serie de elementos posibles. En el caso especial en el que solicitamos que todos los elementos de la primera lista pertenezcan a la segunda lista, se pueden determinar los "valores faltantes" (si los hay).

missingValues([ ],_,[ ]). 
missingValues([H|T],L,K) :- 
    member(H,L), 
    !, 
    missingValues(T,L,K). 
missingValues([H|T],L,[H|K]) :- 
    missingValues(T,L,K). 

Aquí la recursión "se mueve" artículos de la primera lista de entrada a la salida de "objetos perdidos" tercera lista si y sólo si no aparecen en la segunda lista.

Una nota final acerca de sus preguntas se refiere a la notación. En Prolog las variables son identificadores que comienzan con una letra mayúscula o un guión bajo, por lo que el uso de A1, A2, etc. como elementos en la lista se dirige a problemas si se tratan como "incógnitas" en lugar de (como supongo que quiso decir) átomos distintos (constantes). Cambiar a letras minúsculas resolvería eso.