如何使用fold_right創建編碼運行長度的函數？

Question

我創建了一個函數和幫助器函數，用於查找列表中重複元素的數量以及這些元素的含義。

let rec _encode l x = 
    match l with 
    | [] -> 0 
    | head::rest -> (if head = x then 1 else 0) + encode rest x 

let encode l x = ((_encode l x), x) 

在這種情況下，我必須指定元素是什麼它來搜索。

所以這是一個兩部分問題。 1）我該怎麼做才能返回元組列表，格式爲(int * 'a) list，其中int是rep的編號，'a是重複的元素。

2）我將如何使用fold_right實現這個？

我想沿着線的東西：

let encode (l : 'a list) : (int * 'a) list = fold_right (fun (x,hd) lst -> 
    match x with 
    | [] -> 0 
    | hd :: rest -> if hd x then (x+1, hd) else (x, hd)) l [] 

Answer 1

你嘗試看起來很困惑：

• 它不使用lst，hd（第一個），或rest。
• x用作列表（match x with []）和數字（x+1）。
• x（list）的元素是返回布爾值的函數？ （... hd::rest -> ... if hd x）
• 該函數有時會返回一個數字（0），有時還會返回一個元組（(x, hd)）。

以下是我會做：

let encode l = 
    let f x = function 
       | (n, y) :: zs when x = y -> (n + 1, y) :: zs 
       | zs      -> (1, x) :: zs 
    in 
    fold_right f l [] 

這是一樣的：

let encode l = 
    let f x z = match z with 
       | (n, y) :: zs when x = y -> (n + 1, y) :: zs 
       | zs      -> (1, x) :: zs 
    in 
    fold_right f l [] 

這是一樣的：

let encode l = 
    fold_right (fun x z -> 
     match z with 
     | (n, y) :: zs when x = y -> (n + 1, y) :: zs 
     | zs      -> (1, x) :: zs 
    ) l []