Làm cách nào để triển khai danh sách đuôi đệ quy?

Question

Một chức năng đơn giản như thế này append (trong F #):

let rec app s t = 
    match s with 
     | [] -> t 
     | (x::ss) -> x :: (app ss t) 

sẽ sụp đổ khi s trở nên lớn, vì chức năng không phải là đệ quy đuôi. Tôi nhận thấy rằng chức năng nối thêm tiêu chuẩn của F # không sụp đổ với các danh sách lớn, vì vậy nó phải được thực hiện khác nhau. Vì vậy, tôi tự hỏi: Làm thế nào để một định nghĩa đuôi đệ quy của phụ thêm như thế nào? Tôi đã đưa ra một cái gì đó như thế này:

let rec comb s t = 
    match s with 
     | [] -> t 
     | (x::ss) -> comb ss (x::t) 
let app2 s t = comb (List.rev s) t 

hoạt động, nhưng có vẻ hơi lạ. Có một định nghĩa thanh lịch hơn?

Answer 1

truyền thống (không đuôi-đệ quy)

let rec append a b = 
    match a, b with 
    | [], ys -> ys 
    | x::xs, ys -> x::append xs ys 

Với một ắc (đuôi-đệ quy)

let append2 a b = 
    let rec loop acc = function 
     | [] -> acc 
     | x::xs -> loop (x::acc) xs 
    loop b (List.rev a) 

Với continuations (đuôi-đệ quy)

let append3 a b = 
    let rec append = function 
     | cont, [], ys -> cont ys 
     | cont, x::xs, ys -> append ((fun acc -> cont (x::acc)), xs, ys) 
    append(id, a, b) 

Khá thẳng về phía trước của nó để chuyển đổi bất kỳ chức năng đệ quy không đuôi nào để đệ quy với các phép tiếp tục, nhưng cá nhân tôi thích các bộ tích lũy để có thể đọc thẳng về phía trước.

Answer 2

Nhìn lướt qua các nguồn F #, có vẻ như đuôi là nội bộ có thể thay đổi. Một giải pháp đơn giản sẽ là đảo ngược danh sách đầu tiên trước khi đưa các phần tử của nó vào danh sách thứ hai. Điều đó, cùng với việc đảo ngược danh sách, là tầm thường để triển khai đuôi đệ quy.

Answer 3

Ngoài những gì Juliet gửi:

Sử dụng chuỗi biểu thức
Bên trong, biểu thức chuỗi tạo đuôi-đệ quy mã, vì vậy đây chỉ hoạt động tốt.

let append xs ys = 
    [ yield! xs 
    yield! ys ] 

Sử dụng các loại NET có thể thay đổi
David nói rằng F # danh sách có thể được biến đổi - đó là tuy nhiên chỉ giới hạn F thư viện # lõi (và tính năng không thể được sử dụng bởi người dùng, vì nó phá vỡ các khái niệm chức năng) . Bạn có thể sử dụng loại dữ liệu .NET có thể thay đổi để triển khai phiên bản dựa trên đột biến:

let append (xs:'a[]) (ys:'a[]) = 
    let ra = new ResizeArray<_>(xs) 
    for y in ys do ra.Add(y) 
    ra |> List.ofSeq 

Điều này có thể hữu ích trong một số trường hợp, nhưng tôi thường tránh đột biến trong mã F #.