F # xây dựng một danh sách/mảng các giá trị + bản sao liên tiếp

Question

tôi cần để đóng gói dữ liệu như thế này:

let data = [1; 2; 2; 3; 2; 2; 2; 4] 
let packed = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)] 

đâu từng hạng mục nói bao nhiêu lần nó tồn tại trước đó vài tháng. Tuy nhiên, nó phải làm việc với các bản sao không liền kề.

Tôi có thể làm việc này với mã bắt buộc cổ điển, nhưng tự hỏi làm thế nào để thực hiện chức năng này.

Ngoài ra, Seq.countBy không hoạt động bởi vì nó mất trong tài khoản của tất cả các giá trị

Answer 1

Nếu bạn đã có một phiên bản bắt buộc, bạn có thể follow a set of small steps to refector to a recursive implementation.

Recursion

Trong khi tôi không biết những gì phiên bản bắt buộc của bạn trông như thế nào, đây là một phiên bản đệ quy:

let pack xs = 
    let rec imp acc = function 
    | [] -> acc 
    | h::t -> 
     match acc with 
     | [] -> imp [(h, 1)] t 
     | (i, count) :: ta -> 
      if h = i 
      then imp ((i, count + 1) :: ta) t 
      else imp ((h, 1) :: (i, count) :: ta) t 
    xs |> imp [] |> List.rev 

Chức năng này có kiểu 'a list -> ('a * int) list when 'a : equality. Nó sử dụng một chức năng thực hiện riêng được gọi là imp để thực hiện công việc. Chức năng này là đệ quy, và đề một bộ tích lũy (gọi là acc) trong suốt. Bộ tích lũy này là danh sách kết quả, có loại ('a * int) list.

Nếu danh sách ắc là trống rỗng, người đứng đầu danh sách ban đầu (h), cũng như các tính 1, được tạo ra như một tuple là yếu tố duy nhất của ắc cập nhật, và các chức năng imp được đệ quy gọi với bộ tích lũy được cập nhật đó.

Nếu bộ tích lũy đã chứa ít nhất một phần tử, phần tử được trích xuất thông qua khớp mẫu và phần tử trong bộ tóan đó (i) được so sánh với h. Nếu h = i, bộ tích lũy được cập nhật; nếu không, một tuple mới sẽ được chấp nhận trên acc. Trong cả hai trường hợp, mặc dù, imp được gọi đệ quy với bộ tích lũy mới.

Bạn có thể gọi nó với một danh sách tương đương với tuple ban đầu của bạn như thế này:

> pack [1; 2; 2; 3; 2; 2; 2; 4];; 
val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)] 

Fold

Một khi bạn có một phiên bản đệ quy, bạn thường có công thức cho một phiên bản sử dụng một gập lại. Trong trường hợp này, vì chức năng trên pack phải đảo ngược bộ tích lũy cuối cùng (sử dụng List.rev), phải gấp là phù hợp nhất.Trong F #, điều này được thực hiện với sự tích hợp List.foldBack chức năng:

let pack' xs = 
    let imp x = function 
     | (i, count) :: ta when i = x -> (i, count + 1) :: ta 
     | ta -> (x, 1) :: ta 
    List.foldBack imp xs [] 

Trong trường hợp này, các hàm được chuyển vào List.foldBack là một chút quá phức tạp để vượt qua như một chức năng ẩn danh, vì vậy tôi đã chọn để xác định nó như là một chức năng bên trong riêng. Nó tương đương với hàm đệ quy imp được sử dụng bởi hàm pack ở trên, nhưng bạn sẽ nhận thấy rằng nó không phải gọi chính nó một cách đệ quy. Thay vào đó, nó chỉ phải trả về giá trị mới cho bộ tích lũy.

Kết quả là như nhau:

> pack' [1; 2; 2; 3; 2; 2; 2; 4];; 
val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)] 

Answer 2

Giải pháp của tôi giả bộ sưu tập data là một danh sách. Nếu có nó như là một tuple (theo ví dụ của bạn) là cố ý thì giải pháp của tôi để làm việc các tuple đã được chuyển đổi thành một danh sách (một ví dụ làm thế nào để làm điều đó có thể được tìm thấy here).

let groupFunc list = 
    let rec groupFuncRec acc lst init count = 
     match lst with 
     | [] -> List.rev acc 
     | head::[] when head = init 
      -> groupFuncRec ((init, count)::acc) [] 0 0 
     | head::[] when head <> init 
      -> groupFuncRec ((head, 1)::acc) [] 0 0 
     | head::tail when head = init 
      -> groupFuncRec acc tail head (count+1) 
     | head::tail when head <> init 
      -> groupFuncRec ((init, count)::acc) tail head 1 
    let t = List.tail list 
    let h = List.head list 
    groupFuncRec [] t h 1 

Khi tôi chạy các chức năng trên dữ liệu mẫu của bạn tôi lấy lại kết quả mong đợi:

list = [(1, 1); (2, 2); (3, 1); (4, 1)] 

Answer 3

Bạn có thể nhận Seq.countBy để làm việc bằng cách bao gồm một số thông tin vị trí trong đối số của nó. Tất nhiên, bạn cần sau đó ánh xạ trở lại dữ liệu gốc của bạn.

[1; 2; 2; 3; 2; 2; 2; 4] 
|> Seq.scan (fun (s, i) x -> 
    match s with 
    | Some p when p = x -> Some x, i 
    | _ -> Some x, i + 1) (None, 0) 
|> Seq.countBy id 
|> Seq.choose (function 
| (Some t, _), n -> Some(t, n) 
| _ -> None) 
|> Seq.toList 
// val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]