Come posso concatenare la lista di Erlang concatenata senza utilizzare il modulo elenchi?

Question

Il libro che sto leggendo su Erlang ha esercizi sul retro e uno è quello di ricreare gli elenchi: aggiungere la funzione.

Potrei farlo semplicemente usando l'operatore ++, ma non è molto lento? E penso che il punto dell'esercizio sia farlo usando le operazioni di lista che scrivo.

Finora l'unico approccio che mi veniva in mente è quello di fare qualcosa di simile:

concat([], _, Results)-> 
    Results; 
concat(_, [], Results)-> 
    Results; 
concat([Ah|At],B,Results) -> 
    concat(At,B,[Ah|Results]). 

Ma so che questo non è corretto ...

Qualche suggerimento su come andare a fare questo?

EDIT: Per chiarire la domanda, ecco un ingresso e un'uscita esempio:

ingresso: [[1,2,3], [], [4,5], [6]] uscita: [1,2,3,4,5,6]

Dopo aver lavorato un po ', mi si avvicinò con questo codice così:

append([A|[B|[T|[]]]]) -> 
    append([A++B|T]); 
append([H|T]) -> 
    H++T. 

Tuttavia, questo funziona solo per quando la lista è la dimensione 3 Come posso modificarlo in modo che funzioni per una data quantità di elenchi di dimensioni casuali?

Answer 1

Hai solo bisogno di due parametri per la tua funzione concat, dato che ti verrà aggiunto uno dei parametri e questo è quello che alla fine restituirai. Qualcosa di simile (non testata):

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

L'++ è l'operatore di aggiunta, si sta andando ad avere a che fare che, per essere efficace.

(L'idea di quanto sopra è di restituire il parametro di sinistra se non ne è rimasto più, o di richiamare dopo aver spostato uno degli elementi da destra a sinistra). Probabilmente ci sono più efficienze nel fare l'append al contrario e infine invertire la risposta ma hey ...)

(Ho appena visto la tua modifica, e la mia ovviamente funziona solo per due cose da aggiungere, ma puoi recitare attraverso sopra la funzione per ogni elemento nella vostra lista di liste ...)

Answer 2

++ è lento solo se usato in modo errato, usato con cura è veloce come qualsiasi cosa che si possa craftare a mano. Devi assicurarti di lavorare attraverso l'elenco nella direzione corretta, altrimenti l'appendente risultante è O (N^2). Quando facciamo X ++ Y, dobbiamo fare una copia di X e quindi anteporla a Y che non è copiata.

In questa funzione, l'accumulatore appare sul lato sinistro del ++, quindi l'append non è efficiente.

concatl(Lst) -> 
    concatl(Lst, []). 
concatl([], Acc) -> 
    Acc; 
concatl([H|T], Acc) -> 
    concatl(T, AcC++ H). 

Questa funzione si comporta molto meglio, anche se non è ricorsiva della coda.

concat([]) -> []; 
concat([H|T]) -> 
    H ++ concat(T). 

In questo caso riscrittura di essere ricorsiva coda è solo un modesto miglioramento:

concat2(Lst) -> 
    concat2(lists:reverse(Lst), []). 
concat2([], Acc) -> Acc; 
concat2([H|T], Acc) -> 
    concat2(T, H ++ Acc). 

I tempi su un grande ingresso lista mostrano quanto sia grande il miglioramento è. (I tempi sono in microsecondi.)

41> Time(fun() -> test:concatl([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end). 
14539061 
40> Time(fun() -> test:concat([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end). 
245356 
42> Time(fun() -> test:concat2([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end). 
211571 

Answer 3

Un approccio pulito è quello di utilizzare lists:foldr,

concat(A,B) -> 
    lists:foldr(fun(X,XS) -> [X|XS] end, B, A). 

concat(XS) -> 
    lists:foldr(fun concat/2, [], XS). 

E 'anche una buona esercitazione per scrivere la propria funzione foldr ...

Answer 4

-module(functional). 
    -export([my_append/2,helper/2]). 

    my_append(L1,L2) -> 
     % concatenates lists L1 and L2 
     functional:helper(lists:reverse(L1),L2). 
    helper(L1,L2) -> 
     if 
      L1 == [] -> L2; 
      L2 == [] -> L1; 
      true  -> [H1|T1] = L1, 
         functional:helper(T1,[H1|L2]) 
     end.