Jak mogę napisać listę połączeń Erlanga bez użycia modułu list?

Question

Książka, którą czytam o Erlangu, ma ćwiczenia z tyłu i jedną jest odtworzenie list: funkcja dołączania.

Mogę to zrobić po prostu używając operatora ++, ale czy to nie jest naprawdę powolne? I myślę, że celem ćwiczenia jest zrobienie tego za pomocą operacji listowych, które piszę.

Dotychczas jedynym podejściem, że mogę myśleć o to, aby zrobić coś takiego:

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

Ale wiem, że jest to błędne ...

jakieś sugestie, jak go o to robi?

Edycja: jest wyjaśnienie, tu przykład wejściowe i wyjściowe:

Wejście: [[1,2,3], [], [4,5], [6]] wyjściowa: [1,2,3,4,5,6] Po pracy chwilę, doszedłem

się z tym kodem, a także:

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

jednak to działa tylko dla gdy lista jest rozmiar 3 W jaki sposób mogę zmodyfikować to tak, aby działało dla dowolnej ilości list o losowej wielkości?

Answer 1

Potrzebujesz tylko dwóch parametrów do swojej funkcji concat, ponieważ będziesz dołączać do jednego z parametrów i to w końcu powrócisz. Coś podobnego (niesprawdzone):

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

++ jest operatorem append, będziesz musiał to zrobić, aby być skuteczne.

(Ideą powyższego jest zwrócenie lewego parametru, jeśli nie mamy już więcej, lub wywołanie ponownie po przeniesieniu jednego z elementów od prawej do lewej). Prawdopodobnie jest więcej usprawnień związanych z robieniem odpowiedzi w odwrotnej kolejności, a na końcu odwrócenie odpowiedzi, ale hej ...)

(Właśnie zobaczyłem twoją edycję, a moja oczywiście działa tylko na dwie rzeczy do dodania, ale możesz rekurencyjnie przejść przez powyższa funkcja dla każdego elementu na liście list ...)

Answer 2

++ jest powolna tylko wtedy, gdy jest używana nieprawidłowo, używana ostrożnie, jest tak szybka, jak wszystko, co możesz wykonać ręcznie. Musisz upewnić się, że przeglądasz listę we właściwym kierunku, w przeciwnym razie wynikowy dodatek to O (N^2). Kiedy wykonujemy X ++ Y, musimy zrobić kopię X, a następnie dołączyć ją do Y, która nie jest kopiowana.

W tej funkcji akumulator pojawia się po lewej stronie ++, więc załącznik nie jest wydajny.

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

Ta funkcja działa znacznie lepiej, mimo że nie jest rekurencyjna.

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

W tym przypadku przepisywania za ogon rekurencyjnej jest tylko niewielka poprawa:

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

Te czasy na dużym wejściowego listy pokazują, jak ogromna poprawa jest. (Czasy są w mikrosekundach.)

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

Jeden schludny podejściem jest użycie lists:foldr,

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

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

Jest to także dobre ćwiczenia napisać własną funkcję 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.