Appiattisci un elenco di elenchi annidati in Erlang

Question

Sto lavorando sugli esercizi in Programmazione Erlang.

La domanda è

scrivere una funzione che, data una lista di liste nidificate, restituirà una lista piatta.

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

suggerimento: utilizzare concatenate per risolvere flatten.

E qui è la mia funzione concatenate

%% 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). 

voglio davvero sapere un modo elegante per implementare flatten. Ho passato ore a risolvere questo esercizio.

UPDATE: Ho dimenticato il prerequisito più importante. È possibile risolvere questo problema con solo ricorsione e corrispondenza modello?

Answer 1

vorrei provare questo modo

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]). 

testare

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

UPD: o in questo modo, senza protezioni e retromarcia, solo le chiamate ricorsive e pattern matching.

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 chiave della domanda è "divide et impera".

Un'altra funzione aggiuntiva "elenca: reverse" e un operatore "++" vengono utilizzati per il salvataggio del tempo di programmazione.

 

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,[]). 

per il test: Test: my_flat ([[1, [2, [3], []]], [[[4]]], [5,6]], []) .

Answer 3

Alcune soluzioni diverse, sempre più intelligenti e più intelligente:

%% 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]. 

Questi sono tutti solo con pattern matching e la ricorsione, ma possono essere migliorati con alcuni test di tipo guardia. L'utilizzo di ++ è inefficiente poiché copia l'elenco ogni volta. Il modulo lists utilizza una versione dell'ultimo con un test del tipo di protezione anziché l'ultima clausola.

Answer 4

abbastanza conciso e semplice versione:

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

concatenate/1, come definito nel libro funziona come una funzione appiattire che appiattisce verso il basso un solo livello. (, [[[1]],[[2]]] diventa [[1],[2]], ecc.) La strategia suggerita nel suggerimento è di appiattirsi completamente non definendo nuova logica in appiattimento/1 ma utilizzando concatenato/1 nelle chiamate ricorsive di appiattimento/1.

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.