reemplazar - Prolog: partición entera de lista de elementos por su paridad

listas en prolog codigo fuente

Question

Escribe un predicado que toma como entrada una lista de enteros, L , y produce dos listas: la lista que contiene los elementos pares de L y la lista de elementos impares de L

?- separate_parity([1,2,3,4,5,6], Es, Os).
Es = [2,4,6], Os = [1,3,5] ? ;
no

Answer 1

Puede usar clpfd para esto. De esta manera obtienes una relación pura:

:- use_module(library(clpfd)).
list_evens_odds([], [], []).
list_evens_odds([E|Zs], [E|Es], Os) :-
   0 #= E mod 2,
   list_evens_odds(Zs, Es, Os).
list_evens_odds([E|Zs], Es, [E|Os]) :-
   1 #= E mod 2,
   list_evens_odds(Zs, Es, Os).

Puede usar esto no solo para dividir una lista en pares y probabilidades. Pero puedes ir aún más lejos. La siguiente interacción es con SWI, pero obtiene similar en SICStus con asserta(clpfd:full_answer) .

?- list_evens_odds([1, 2, 3, 4, 5, 6], Es, Os). Es = [2, 4, 6], Os = [1, 3, 5] ; false. ?- Zs = [A,B,C], list_evens_odds(Zs, Es, Os). Zs = [A, B, C], Es = [A, B, C], Os = [], A mod 2#=0, B mod 2#=0, C mod 2#=0 ; Zs = [A, B, C], Es = [A, B], Os = [C], A mod 2#=0, B mod 2#=0, C mod 2#=1 ; Zs = [A, B, C], Es = [A, C], Os = [B], A mod 2#=0, B mod 2#=1, C mod 2#=0 ... ?- Es = [E], Os = [O], list_evens_odds(Zs, Es, Os). Es = [E], Os = [O], Zs = [E, O], E mod 2#=0, O mod 2#=1 ; Es = [E], Os = [O], Zs = [O, E], E mod 2#=0, O mod 2#=1 ; false.

El siguiente es probablemente el más irritante: aquí, nos preguntamos si hay un EO entero que sea par e impar. Ciertamente, ese número entero no puede existir. ¡Pero aún tenemos dos respuestas!

?- EOs=[EO], list_evens_odds(Zs, EOs, EOs). EOs = [EO], Zs = [EO, EO], EO mod 2#=1, EO mod 2#=0 ; EOs = [EO], Zs = [EO, EO], EO mod 2#=0, EO mod 2#=1 ; false.

Esto ilustra la diferencia entre respuestas y soluciones. Aquí tenemos dos respuestas, pero ambas no contienen una solución. La mayoría de las veces una respuesta contiene una o más soluciones, pero tampoco puede contener ninguna como en este caso. Tales respuestas a veces se llaman inconsistencias.

Las inconsistencias no necesariamente se consideran un error de una implementación. Son más bien un compromiso de ingeniería: garantizar la coherencia puede ser muy costoso en comparación con los beneficios reales. Y: Prolog no produce una respuesta incorrecta: se muestra la condición que tiene que mantener. Incluso si esa condición resulta ser falsa.

Answer 2

Solo use la recursión estructural en las listas. Anote las equivalencias para cada caso mutuamente exclusivo:

parity_partition([A|B], [A|X], Y):- 0 is A mod 2, parity_partition(B,X,Y).
parity_partition([A|B], X, [A|Y]):- 1 is A mod 2, parity_partition(B,X,Y).
parity_partition([],[],[]).

Esto significa: relación parity_partition(L,E,O) contiene ,

1. en caso de que L=[A|B] y A sea ​​par, cuando E=[A|X] , O=Y y la parity_partition(B,X,Y) relación parity_partition(B,X,Y) cumple.
2. en caso de que L=[A|B] y A sea ​​impar, cuando E=X , O=[A|Y] y la parity_partition(B,X,Y) relación parity_partition(B,X,Y) cumple.
3. en caso L=[] , cuando E=[] y O=[] .

Simplemente escribir estas equivalencias nos da el programa Prolog para resolver esto.

Operacionalmente, esto significa: separar una lista L en una lista de pares E y una lista de probabilidades O ,

1. if `L` is a non-empty list `[A|B]`, 1a. if `A` is even, allocate new list node for `E=[H|T]`, set its data field `H=A`, and continue separating the rest of input list `B` into `T` and `O` ; or 1b. if `A` is odd, allocate new list node for `O=[H|T]`, set its data field `H=A`, and continue separating the rest of input list `B` into `E` and `T` ; or 2. if `L` is an empty list, set both `E` and `O` to be empty lists

la secuencia real de operaciones puede ser un poco diferente pero conceptualmente igual:

1. try to unify L=[A|B], E=[A|X]. If not, go to 2. 1a. check if A is even. If not, abandon the instantiations made as part of unifications, and go to 2. 1b. Continue with B, X, and the same O: use B as L, X as E, and go to 1. 2. try to unify L=[A|B], O=[A|Y]. If not, go to 3. 2a. check if A is odd. If not, abandon the instantiations made as part of unifications, and go to 3. 2b. Continue with B, Y, and the same E: use B as L, Y as O, and go to 1. 3. Unify L,E,O with [].

Answer 3

la respuesta de @Will Ness es buena y detallada. Añadiré la posibilidad, si su Prolog lo ofrece, de usar una orden interna de ''orden superior'' (es decir, un predicado que recibe un predicado como argumento):

separate_parity(L, E, O) :-
    partition(is_even, L, E, O).
is_even(N) :- N mod 2 =:= 0.

Puede encontrar aquí una breve explicación para el builtin.

Answer 4

Esta respuesta se basa en clpfd , meta-predicate tpartition/4 y zodd_t/2 test zodd_t/2 :

:- use_module(library(clpfd)).

Usando tpartition/4 en combinación con zodd_t/2 podemos simplemente escribir:

?- tpartition(zodd_truth,[1,2,3,4,5,6],Es,Os).
Es = [1,3,5], Os = [2,4,6].                 % succeeds deterministically