如何使用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 []