Как устранить последовательные дубликаты элементов списка?

Question

(в Окамле)

Это решение работает

let compress l =
let rec compress_2 l e =
    match l with
        | [] -> [e]
        | h::t -> if (h=e)
                    then (compress_2 t e)
                    else e::(compress_2 t)
in
    match l with
        | [] -> []
        | h::t -> compress_2 t h;;

Но почему это решение не работает?

let rec compress (l: 'a list) : 'a list =
match l with
    | [] -> []
    | h::[] -> [h]
    | h1::h2::t -> if h1=h2 then h2::(compress t) else h1::h2::(compress t) ;;

Answer 1

В этом случае

| h1::h2::t -> if h1=h2 then h2::(compress t) else h1::h2::(compress t) ;;

Вы не заметите дубликат, если h2 совпадает с заголовком t. Вам нужно передать (h2 :: t) в рекурсивных вызовах на compress.

Я написал эту функцию много раз (возможно, кандидат в стандартную библиотеку List). Вот как я обычно пишу это (избегая лишних минусов или двух):

let rec compress l =
    match l with
    | [] -> []
    | [_] -> l
    | h1 :: ((h2 :: _) as tail) ->
        if h1 = h2 then compress tail else h1 :: compress tail

Это не хвостовая рекурсия, поэтому он занимает линейное количество стекового пространства. Это хорошо, если вы знаете, что ваши списки, как правило, довольно короткие.

Answer 2

ExtLib (и, следовательно, батареи) имеют эту функцию - даже с дополнительным параметром для передачи в вашу собственную функцию равенства: http://nit.gforge.inria.fr/extlib/ExtList.List.html#VALunique

Если вы хотите бросить свой собственный, попробуйте это:

let compress eq ls =
   (* acc: accumulator; x: the optional comparison value; xs: the not-unique list *)
   let rec remdup acc x xs =
    match (x, xs) with
    | (_, []) -> acc
    | (None, y::ys) -> remdup (y::acc) (Some y) ys
    | (Some z, y::ys) -> if eq z y then remdup acc x ys else remdup (y::acc) (Some y) ys
   in
   (* need to reverse the final list as we appended in front of the accumulator *)
   List.rev (remdup [] None ls)

, а затем просто

let unique = compress (=) [1; 1; 1; 2; 3; 3; 4; 5; 6; 6; 7; 8; 9; 9; 9]