Kết hợp hai danh sách

Question

Tôi đang tìm cách hợp nhất 2 danh sách trong F # theo cách hoàn toàn có chức năng. Tôi gặp khó khăn trong việc hiểu cú pháp.

Hãy nói rằng tôi có một tuple ([5;3;8],[2;9;4])

Khi tôi gọi hàm, nó sẽ trả về [5;2;3;9;8;4]

Đây là lý do tại sao tôi có cho đến nay, đó là sai Tôi chắc chắn. Nếu ai đó có thể giải thích nó một cách đơn giản, tôi sẽ biết ơn.

let rec interleave (xs,ys) = function 
|([], ys) -> ys 
|(x::xs, y::ys) -> x :: y:: interleave (xs,ys) 

Answer 1

Chức năng của bạn là gần như. let f = function là viết tắt của let f x = match x with vì vậy bạn không cần args rõ ràng. Ngoài ra, thuật toán của bạn cần một số tinh chỉnh.

let rec interleave = function //same as: let rec interleave (xs, ys) = match xs, ys with 
    |([], ys) -> ys 
    |(xs, []) -> xs 
    |(x::xs, y::ys) -> x :: y :: interleave (xs,ys) 

interleave ([5;3;8],[2;9;4]) //output: [5; 2; 3; 9; 8; 4] 

Answer 2

Một điểm quan trọng là chức năng không chính xác. Không thành công với đầu vào ([1;2;3], []) vì bạn đã bỏ lỡ trường hợp (xs, []) trong đối sánh mẫu. Hơn nữa, các đối số tốt hơn ở dạng đã được xử lý để dễ sử dụng hơn với ứng dụng một phần. Dưới đây là phiên bản chỉnh:

let rec interleave xs ys = 
    match xs, ys with 
    | [], ys -> ys 
    | xs, [] -> xs 
    | x::xs', y::ys' -> x::y::interleave xs' ys' 

Bạn có thể thấy rằng các chức năng là không đuôi-đệ quy vì nó áp dụng nhược điểm (::) constructor hai lần sau khi cuộc gọi đệ quy quay trở lại. Một cách thú vị để làm cho nó đuôi-đệ quy được sử dụng biểu hiện trình tự:

let interleave xs ys = 
    let rec loop xs ys = 
     seq { 
      match xs, ys with 
      | [], ys -> yield! ys 
      | xs, [] -> yield! xs 
      | x::xs', y::ys' -> 
        yield x 
        yield y 
        yield! loop xs' ys' 
      } 
    loop xs ys |> List.ofSeq 

Answer 3

Bạn có thể sử dụng cơ hội này để xác định một hàm bậc cao tổng quát hơn - zipWith, và sau đó thực hiện interleave sử dụng nó.

let rec zipWith f xlist ylist = 
    match f, xlist, ylist with 
    | f, (x :: xs), (y :: ys) -> f x y :: zipWith f xs ys 
    | _, _, _ -> [] 

let interleave xs ys = zipWith (fun a b -> [a; b]) xs ys |> List.concat 

Edit:

Như @pad nói dưới đây, F # đã có zipWith dưới cái tên List.map2. Vì vậy, bạn có thể viết lại interleave như sau:

let interleave xs ys = List.map2 (fun a b -> [a; b]) xs ys |> List.concat 

Answer 4

Từ OP nó không rõ ràng những gì sẽ xảy ra nếu danh sách có độ dài khác nhau, nhưng đây là một generic, đuôi-đệ quy thực hiện tiêu thụ đầy đủ cả hai danh sách:

// 'a list -> 'a list -> 'a list 
let interleave xs ys = 
    let rec imp xs ys acc = 
     match xs, ys with 
     | [], [] -> acc 
     | x::xs, [] -> imp xs [] (x::acc) 
     | [], y::ys -> imp [] ys (y::acc) 
     | x::xs, y::ys -> imp xs ys (y::x::acc) 
    imp xs ys [] |> List.rev 

Ví dụ:

> interleave [5;3;8] [2;9;4];; 
val it : int list = [5; 2; 3; 9; 8; 4] 
> interleave [] [1..3];; 
val it : int list = [1; 2; 3] 
> interleave [1..3] [42];; 
val it : int list = [1; 42; 2; 3] 
> interleave [1..3] [42;1337];; 
val it : int list = [1; 42; 2; 1337; 3] 
> interleave [42; 1337] [1..3];; 
val it : int list = [42; 1; 1337; 2; 3]