CODEWITHSUNDEEP
ocaml
kevgathuku
kevgathuku

Reputation: 348

How to count the number of successive duplicates in Ocaml

I'm trying to write a function that takes in a list, and returns the number of successive duplicate elements in the list.

For example, given [1;2;3;3;4;4;5], the function should return 2

This is my initial implementation, but unfortunately it always returns 0. I'm not quite sure where the bug lies. Any help on how to improve it will be highly appreciated.

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)

Upvotes: 1

Views: 624

Answers (2)

Chris
Chris

Reputation: 36680

Late answer, but as a further suggestion, we can decompose this problem.

Let's get pairs.

# 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)]

And now let's define count that counts values in a list which return true for a predicate function.

# 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

But this isn't very efficient, as we have to generate a whole list of pairs and then iterate over it despite the fact that once we're done with a pair we don't really care about it again. Since this question was asked OCaml 4.07+ have the Seq module which will allow us to make this a lazy operation and avoid the need to keep an entire list in memory.

# 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

Upvotes: 0

Bergi
Bergi

Reputation: 665564

In the end, you'll want to return the accumulator with the count instead of 0 always:

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)

Upvotes: 1

Related Questions