Dividir una lista en la mitad

Question

necesito para definir brecha para que [1,2,3,4,5] lista se divide en:

a = [1,2,3} 

b = [4,5] 

Recibo un error que dice "Arguments are not sufficiently instantiated", y no sé lo suficiente sobre el lenguaje de averiguar cuál es mi problema, o si mi diseño es incluso correcto. Cualquier orientación sería apreciada.

Así que esto es lo que tengo hasta ahora:

append([],L2,L2). 
append([H|T],L2,[H|L3]) :- append(T,L2,L3). 

lengthIs([],N). 
lengthIs([H|T],N) :- lengthIs(T,M), N is M+1. 

divide([],[],[]). 
divide([H|T],L2,L3) :- 
    ( lengthIs(L2, M) < lengthIs(L1,N)/2 
    -> divide(T, append(L2, H, X), L3) 
    ; divide(T, L2, append(L3,H,Y)) 
    ). 

Answer 1

Vamos a darle el predicado un nombre más relacional: list_half_half/3

list_half_half(Xs, Ys, Zs) :- 
    length(Xs, N), 
    H is N - N // 2, 
    length(Ys, H), 
    append(Ys, Zs, Xs). 

length/2 y append/3 están predefinidos en prácticamente todos los prólogos recientes.

Esta es GNU Prolog:

| ?- append(L,_,[a,b,c,d]), list_half_half(L,H1,H2). 

H1 = [] 
H2 = [] 
L = [] ? ; 

H1 = [a] 
H2 = [] 
L = [a] ? ; 

H1 = [a] 
H2 = [b] 
L = [a,b] ? ; 

H1 = [a,b] 
H2 = [c] 
L = [a,b,c] ? ; 

H1 = [a,b] 
H2 = [c,d] 
L = [a,b,c,d] 

Answer 2

append es un predicado predefinido, por lo que podría ser el problema: http://en.wikibooks.org/wiki/Prolog/Lists#The_append_predicate

También nunca definió 'N' en lengthis - te necesita establecer la lista vacía como 0, no N/ También es probable que haya una función de tamaño

El subrayado le dice a Prolog que no nos importa ese bit en esa definición de predicado.

Algo como esto debería funcionar

divide(L1,L2,L3):- append(L2,L3,L1), 
        samesize(L2,L3). 
divide(L1,L2,L3):- append(L2,L3,L1), 
        onebigger(L2,L3). 
samesize(A,B):- size(A,N), 
        size(B,N). 
onebigger(A,[_|T]):- size(A,N), 
        size(T,N). 
size([],0). 
size([H|T],N):- size(T,M+1). 

Answer 3

No hay necesidad de comprobar los tamaños. Sólo hacerlo de esta manera:

div([],[],[]). 
div([A],[A],[]). 
div([A,B|T],[A|X],[B|Y]) :- div(T,X,Y). 

Answer 4

Sin duda, el efecto de este código (lengthIs(L2, M) < lengthIs(L1,N)/2 -> ...) no es lo que espera: no se puede comparar los números, pero los términos. Usted debe escribir de esta manera:

lengthIs(L2, M), lengthIs(L1, N), M < N/2 -> ... 

Otro error tipográfico como error: la primera cláusula del lengthis/2 debe leer

lengthIs([],0). 

Answer 5

Ésta es la solución más eficiente conforme a su especificación para la mayoría de las implementaciones Prolog:

divide(L, A, B) :- 
    divide1(L, L, A, B). 

divide1([], L, [], L). 
divide1([_|T], [H|L], [H|A], B) :- 
    divide2(T, L, A, B). 

divide2([], L, [], L). 
divide2([_|T], L, A, B) :- 
    divide1(T, L, A, B). 

Si no le importa que los elementos a entrar en las listas secundarias en la medida que son de longitud similar (como en la solución de Konstantin posterior Weitz), entonces ca n uso:

divide([], [], []). 
divide([H|T], [H|A], B) :- divide(T, B, A). 

Answer 6

Otra respuesta, usos Backtracking mucho, no es de buen calidad, sin embargo. append y length se supone que son predefinidos:

divide(A,B,C):- 
    append(B,C,A), 
    length(B,B_Length), 
    length(C,C_Length), 
    (B_Length = C_Length; 
     B_Length =:= C_Length +1). 

Oh, lo siento, acabamos de ver que esto es una especie de reformulación de la respuesta de Felipe Whitehouse.

Answer 7

Así es como lo hice.Casi sin muebles empotrados:

split_list_in_half(Xs , H , T) :- 
    list_length(X , L) , 
    LL = L - (L // 2) , 
    take_first(Xs , LL , H , T) , 
    . 

list_length(L , N) :- 
    list_length(L , 0 , N) 
    . 

list_length([] , N , N). 
list_length([X|Xs] , T , N) :- 
    T1 is T+1 , 
    list_length(Xs , T1 , N) 
    . 

take_first(Xs , N , Pfx , Sfx) :- 
    take_first(Xs , N , [] , P1 , Sfx) , 
    reverse(P1 , Pfx) 
    . 

take_first([]  , _ , H , H , [] ). 
take_first([X|Xs] , 0 , H , H , [X|Xs]). 
take_first([X|Xs] , N , H1 , H , T  ) :- 
    N > 0 , 
    N1 = N-1 , 
    take_first(Xs , N1 , [X|H1] , H , T) 
    .