Làm thế nào tôi có thể viết danh sách của Erlang nối mà không sử dụng mô-đun danh sách?

Question

Cuốn sách tôi đang đọc về Erlang có bài tập ở mặt sau của nó và một là để tái tạo danh sách: nối thêm chức năng.

Tôi có thể làm điều này chỉ đơn giản bằng cách sử dụng toán tử ++, nhưng điều này có thực sự chậm không? Và tôi nghĩ rằng điểm của bài tập là làm điều đó bằng cách sử dụng các hoạt động danh sách mà tôi viết.

Cho đến nay phương pháp duy nhất mà tôi có thể nghĩ là để làm một cái gì đó như:

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

Nhưng tôi biết điều này là không chính xác ...

Bất kỳ đề xuất về cách đi về việc này?

EDIT: Để làm rõ câu hỏi, đây là một ví dụ đầu vào và đầu ra:

Input: [[1,2,3], [], [4,5], [6]] Output: [1,2,3,4,5,6]

Sau khi làm việc một thời gian, tôi đã đưa ra với mã này cũng như:

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

Tuy nhiên, điều này chỉ làm việc cho khi danh sách là kích thước 3 Làm thế nào tôi có thể sửa đổi điều này để nó hoạt động cho bất kỳ số tiền nhất định của danh sách kích thước ngẫu nhiên?

Answer 1

Bạn chỉ cần hai tham số cho hàm concat của mình, vì bạn sẽ được thêm vào một trong các tham số và đó là những gì bạn sẽ quay trở lại. Một cái gì đó như (chưa được kiểm tra):

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

++ là toán tử nối thêm, bạn sẽ phải làm điều đó để có hiệu quả.

(Ý tưởng ở trên là trả lại tham số bên trái nếu chúng tôi không còn lại hoặc gọi lại sau khi di chuyển một trong các thành phần từ phải sang trái). Có lẽ có nhiều hiệu quả hơn khi thực hiện nối thêm ngược lại và cuối cùng đảo ngược câu trả lời nhưng hey ...)

(Chỉ cần nhìn thấy chỉnh sửa của bạn, và tất nhiên tôi chỉ làm việc cho hai thứ để nối thêm, nhưng bạn có thể recurse thông qua chức năng trên cho mỗi phần tử trong danh sách danh sách của bạn ...)

Answer 2

++ chỉ chậm khi được sử dụng sai, cẩn thận sử dụng nó nhanh như mọi thứ bạn có thể thủ công bằng tay. Bạn phải chắc chắn rằng bạn làm việc thông qua danh sách theo đúng hướng, nếu không kết quả thêm là O (N^2). Khi chúng ta thực hiện X ++ Y, chúng ta phải tạo một bản sao của X và sau đó thêm nó vào Y mà không được sao chép.

Trong chức năng này, bộ tích lũy xuất hiện ở phía bên tay trái của ++, do đó phần nối thêm không hiệu quả.

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

Chức năng này hoạt động tốt hơn nhiều, mặc dù nó không phải đệ quy đuôi.

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

Trong trường hợp này viết lại là đuôi đệ quy chỉ là một sự cải thiện khiêm tốn:

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

Các timings trên một danh sách đầu vào chương trình lớn như thế nào rất lớn cải thiện được. (Thời gian tính bằng micro giây.)

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

Một cách tiếp cận gọn gàng là sử dụng lists:foldr,

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

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

Nó cũng là một excercise tốt để viết chức năng foldr riêng của bạn ...

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.