你如何消除連續重複的列表元素？

此解決方案

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) ;;

來源

2011-12-24 Aspen

關於您的b）解決方案：考慮[1; 2; 2]的結果。它會工作，如果你在列表中留下h2像'else h1 :: compress（h2 :: t）' – lambdapower 2011-12-24 13:21:56

在這種情況下

| 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

這不是尾遞歸，所以它消耗的堆棧空間的線性量。如果你知道你的清單往往很短，這很好。

來源

2011-12-24 05:58:47

謝謝Jeffrey。你能簡要解釋一下「as」是什麼意思嗎？ – Aspen 2011-12-24 18:53:11

這是一種給模式的一部分命名的方法，所以你可以在關聯的表達式中通過名稱來引用它。在'compress'的情況下，它非常有用：您需要訪問不同級別的相同數據結構（一些內部部件和一些內部部件）。它在手冊中稱爲「別名模式」：http://caml.inria.fr/pub/docs/manual-ocaml/patterns.html – 2011-12-24 19:00:13

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 ]

來源

2011-12-24 13:20:19 lambdapower

你如何消除連續重複的列表元素？

回答

相關問題