Listeler modülünü kullanmadan Erlang'ın liste birleştirmesini nasıl yazabilirim?

Question

Erlang hakkında okuduğum kitap onun arkasında egzersizler var ve bir tanesi listeleri yeniden oluşturmak: fonksiyonu ekle.

Bunu, yalnızca ++ operatörünü kullanarak yapabilirim, ancak bu gerçekten yavaş değil mi? Ve egzersizin amacı, yazdığım liste işlemlerini kullanarak bunu yapmak olduğunu düşünüyorum. Bunu hakkında gitmek nasıl

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

Ama bu yanlış olduğunu biliyorum ...

Herhangi önerileri: düşünebildiğim

Bugüne kadar sadece bir yaklaşım böyle bir şey yapmak mı?

DÜZENLEME: soru açıklığa kavuşturmak için, burada bir örnek giriş ve çıkışı:

Girdi: [[1,2,3], [], [4,5], [6]] Çıkış: [1,2,3,4,5,6]

bir süre çalıştıktan sonra, ben de bu kod ile geldi: Ancak

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

, liste boyutu 3 olduğunda bu sadece çalışır Herhangi bir miktarda rastgele boyutlandırılmış listeler için çalışmasını nasıl değiştirebilirim?

Answer 1

Parametrelerden birine ekleyeceğiniz ve sonuçta geri dönüş yapacağınız gibi, concat işlevinize yalnızca iki parametreye ihtiyacınız vardır. (Denenmemiş) gibi bir şey:

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

++ ekleme operatörüdür, verimli olmak için bunu yapmak zorunda olacak.

(Yukarıdaki fikir, daha fazla kalmadıysa sol parametreyi döndürmek veya öğelerden birini sağdan sola taşıdıktan sonra tekrar aramaktır). Ek olarak tersi uygulama yapmak ve sonra nihayet cevabı tersine çevirmek için daha fazla verimlilik var ama hey ...)

(Sadece düzenlemenizi gördüm ve benimki sadece ekleyeceğim iki şey için işe yarıyor, ancak listenizdeki her öğe için yukarıdaki işlev ...)

Answer 2

++ yalnızca yanlış kullanıldığında yavaştır, dikkatli bir şekilde kullanılır, el ile yapabileceğiniz her şey kadar hızlıdır. Listede doğru yönde çalıştığınızdan emin olmalısınız, aksi halde sonuç eki O (N^2) olur. X ++ Y yaptığımızda, X'in bir kopyasını yapmalı ve daha sonra kopyalanmayan Y'ye eklemeliyiz.

Bu işlevde, toplayıcının ++ sol tarafında görünür, dolayısıyla ek etkili değildir.

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

Bu işlev, özyinelemeli olmasa bile çok daha iyi performans gösterir. Kuyruk özyinelemeli olarak yeniden Bu durumda

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

sadece mütevazi bir gelişmedir:

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

iyileştirme ne kadar büyük büyük bir giriş liste gösteri zamanlamaları. (Zamanlar mikrosaniyedir.)

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

biri düzgün yaklaşım ...

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

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

Kendi foldr fonksiyonunu yazmak iyi excercise de var, lists:foldr kullanmaktır

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.