Ocaml中如何统计连续重复的次数

Question

我正在尝试编写一个接受列表的函数，并返回列表中连续重复元素的数量。

例如，给定

[1;2;3;3;4;4;5]

，函数应该返回

2

这是我最初的实现，但不幸的是它总是返回

0

。我不太确定错误在哪里。 任何有关如何改进它的帮助将不胜感激。

let rec count_successive_duplicates (lst: int list) (count: int) : (int) =
  match lst with
    | [] | [_]-> 0
    | x :: y :: tl ->
      if x = y then count_successive_duplicates (y::tl) (count + 1) else count_successive_duplicates (y::tl) count
  ;;

let () =
  print_int (count_successive_duplicates [1;2;3;3;4;4;5] 0)

Answer 1

最后，你会想要返回带有计数的累加器而不是

0

总是：

let rec count_successive_duplicates (lst: int list) (count: int) : (int) =
  match lst with
    | [] | [_] -> count
(*                ^^^^^ */)
    | x :: y :: tl -> count_successive_duplicates (y::tl) (count + if x = y then 1 else 0)

Answer 2

似乎我在做一些愚蠢的事情，总是为基本情况返回

0

，而不是计算的计数。以前的版本只是忽略了它收到的计算出的

count

。这现在有效：

let rec count_successive_duplicates lst count : (int) = match lst with
  | [] | [_]-> count
  | x :: y :: tl ->
    if x = y then count_successive_duplicates (y::tl) (count + 1) else count_successive_duplicates (y::tl) count
;;

let () =
  print_int (count_successive_duplicates [1;2;3;3;4;4;5] 0)

Answer 3

迟到的答案，但作为进一步的建议，我们可以分解这个问题。

让我们配对。

# let rec pairs = function
    | [] | [_] -> []
    | a::(b::_ as tl) -> (a, b) :: pairs tl;;
val pairs : 'a list -> ('a * 'a) list = <fun>
# pairs [1;2;3;4;5;5;6;7];;
- : (int * int) list = [(1, 2); (2, 3); (3, 4); (4, 5); (5, 5); (5, 6); (6, 7)]

现在让我们定义

count

计算列表中的值，该列表为谓词函数返回 true。

# let count f lst =
    List.fold_left 
      (fun i x -> if f x then i + 1 else i) 
      0 lst;;
val count : ('a -> bool) -> 'a list -> int = <fun>
# pairs [1;2;3;4;5;5;6;7]
  |> count @@ fun (a, b) -> a = b;;
- : int = 1

但这不是很有效，因为我们必须生成一个完整的对列表，然后然后迭代它，尽管事实上一旦我们完成了对，我们就不再关心它了。由于这个问题被问到 OCaml 4.07+ 有

Seq

模块 这将使我们能够使它成为一个惰性操作并避免将整个列表保存在内存中的需要。

# let pairs_seq lst =
    let rec aux lst () =
      match lst with
      | [] | [_] -> Seq.Nil
      | a::(b::_ as tl) -> Seq.Cons ((a, b), fun () -> aux tl ())
    in
    aux lst;;
val pairs_seq : 'a list -> unit -> ('a * 'a) Seq.node = <fun>
# let rec seq_count f s =
    Seq.fold_left (fun i x -> if f x then i+1 else i) 0 s;;
val seq_count : ('a -> bool) -> 'a Seq.t -> int = <fun>
# [1;2;3;4;5;5;6;7] 
  |> pairs_seq 
  |> seq_count @@ fun (a, b) -> a = b;;
- : int = 1