Aplanar una lista de listas anidadas en Erlang

Question

Estoy trabajando en los ejercicios en Erlang Programming.

La pregunta es

escribir una función que, dada una lista de listas anidadas, devolverá una lista plana.

Ejemplo: flatten([[1,[2,[3],[]]], [[[4]]], [5,6]]) ⇒ [1,2,3,4,5,6].

Pista: use concatenate para resolver flatten.

Y aquí es mi concatenate función

%% concatenate([[1,2,3], [], [4, five]]) ⇒ [1,2,3,4,five]. 
concatenate([X|Xs]) -> concat(X, Xs, []). 
concat([X|Xs], T, L) -> concat(Xs, T, [X|L]); 
concat([], [X|Xs], L) -> concat(X, Xs, L); 
concat([], [], L) -> reverse(L). 

Realmente quiero saber una manera elegante de poner en práctica flatten. Pasé horas resolviendo este ejercicio.

ACTUALIZACIÓN: Olvidé el requisito previo más importante. ¿Es posible resolver este problema con solo recursión y coincidencia de patrón?

Answer 1

me gustaría probar esta manera

flatten(X) -> lists:reverse(flatten(X,[])). 

flatten([],Acc) -> Acc; 
flatten([H|T],Acc) when is_list(H) -> flatten(T, flatten(H,Acc)); 
flatten([H|T],Acc) -> flatten(T,[H|Acc]). 

pruebas

my:flatten([[1,[2,[3],[]]], [[[4]]], [5,6]]). 
[1,2,3,4,5,6] 

UPD: o así, sin guardias y marcha atrás, sólo las llamadas recursivas y la coincidencia de patrones.

flatten(X)    -> flatten(X,[]). 

flatten([],Acc)   -> Acc; 
flatten([[]|T],Acc)  -> flatten(T, Acc); 
flatten([[_|_]=H|T],Acc) -> flatten(T, flatten(H,Acc)); 
flatten([H|T],Acc)  -> flatten(T,Acc++[H]) . 

Answer 2

La clave de la pregunta es "dividir y conquistar".

Otra función adicional "listas: inversa" y un operador "++" se utilizan para guardar el tiempo de programación.

 

my_flat([],Result)-> 
    lists:reverse(Result); 
my_flat([H|T],Result) when is_atom(H) -> 
    case T of 
    []-> 
     my_flat([],[H|Result]); 
    _Else -> 
     my_flat(T,[H|Result]) 
    end; 
my_flat([H|T],Result) when is_number(H)-> 
    case T of 
    []-> 
     my_flat([],[H|Result]); 
    _Else -> 
     my_flat(T,[H|Result]) 
    end; 
my_flat([H|T],Result) -> 
my_flat(H,Result)++my_flat(T,[]). 

para su prueba: Prueba: my_flat ([[1, [2, [3], []]], [[[4]]], [5,6]], []) .

Answer 3

Algunas soluciones diferentes, cada vez más inteligentes y más inteligente:

%% Lift nested lists to the front of the list. 
flatten1([[H|T1]|T2]) -> flatten1([H,T1|T2]); 
flatten1([[]|T]) -> flatten1(T); 
flatten1([E|T]) -> [E|flatten1(T)]; 
flatten1([]) -> []. 

o

%% Keep a list of things todo and put tails onto it. 
flatten2(L) -> flatten2(L, []). 

flatten2([H|T], Todo) -> 
    flatten2(H, [T|Todo]); 
flatten2([], [H|Todo]) -> flatten2(H, Todo); 
flatten2([], []) -> []; 
flatten2(E, Todo) -> [E|flatten2(Todo, [])]. 

o

%% Work from the back and keep a tail of things done. 
flatten3(L) -> flatten3(L, []). 

flatten3([H|T], Tail) -> 
    flatten3(H, flatten3(T, Tail)); 
flatten3([], Tail) -> Tail; 
flatten3(E, Tail) -> [E|Tail]. 

Todos estos son sólo con coincidencia de patrones y la recursividad, pero se pueden mejorar wi Algunas pruebas de tipo de guardia. Usar ++ es ineficaz ya que copia la lista cada vez. El módulo lists utiliza una versión de la última con una prueba de tipo de protección en lugar de la última cláusula.

Answer 4

Bastante concisa y directa Versión:

append([H | T], L) -> [H | append(T, L)]; 
append([], L) -> L. 

flatten([[_|_]=H|T]) -> append(flatten(H), flatten(T)); 
flatten([[]|T]) -> flatten(T); 
flatten([H|T]) -> [H|flatten(T)]; 
flatten([]) -> []. 

Answer 5

concatenar/1 tal como se define en el libro funciona como una función aplanar la que se aplana por un solo nivel. ([[1],[2]] se convierte en [1,2], [[[1]],[[2]]] se convierte en [[1],[2]], etc.). La estrategia sugerida en la sugerencia es aplanar completamente no definiendo nueva lógica en flatten/1 sino usando concatenate/1 en flatten/1 llamadas recursivas.

concatenate(Ls) -> 
    reverse(concatenate(Ls, [])). 

concatenate([], Acc) -> 
    Acc; 
concatenate([[]|Rest], Acc) -> 
    concatenate(Rest, Acc); 
concatenate([[H|T]|Rest], Acc) -> 
    concatenate([T|Rest], [H|Acc]); 
concatenate([H|T], Acc) -> 
    concatenate(T, [H|Acc]). 

flatten(L) -> 
    flatten(L, []). 

flatten([], Acc) -> 
    Acc; 
flatten(L, Acc) -> 
    Concatted = concatenate(L), 
    [Non_lists|Remainder] = find_sublist(Concatted), 
    flatten(Remainder, concatenate([Acc, Non_lists])). 

find_sublist(L) -> 
    find_sublist(L, []). 

find_sublist([], Acc) -> 
    reverse(Acc); 
find_sublist(L = [[_|_]|_], Acc) -> 
    [reverse(Acc)|L]; 
find_sublist([H|T], Acc) -> 
    find_sublist(T, [H|Acc]). 

tests() -> 
    [1,2,3,4,4,5,6,7,8] = flatten([[1,[2,[3],[]]], [[[4,[4]]]], [[5],6], [[[]]], [], [[]], [[[7, 8]]]]), 
    [1,2] = flatten([[1,2]]), 
    [1,2,3] = flatten([[1],[2],[3]]), 
    [1,2,3,4,5,6] = flatten([[1,[2,[3],[]]], [[[4]]], [5,6]]), 
    tests_successful.