リスト要素の連続した重複をどのように排除しますか？

Question

（OCamlでは）このソリューションは

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の頭と同じである場合は、重複して気付くことはありません。再帰的な呼び出しでcompressに を渡し、(h2 :: t)を渡す必要があります。

私はこの関数を何度も書いています（おそらく標準Listライブラリの候補です）。ここで私は通常、（余分な短所または2を避けて）それを書く方法は次のとおりです。

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) 

、次いでだけ

はユニーク=圧縮（=）1せ; 1; 1; 2; 3; 3; 4; 5; 6; 6; 7; 8; 9; 9; 9 ]