OCaml中

Question

更換子列表與另一子表我想更換一個子列表lista與另一子表listb從列表listo以實現以下目的：

let replace_sublist listo lista listb = 

列表0，如果有sublist = lista，然後用listb替換這個子列表。

我發現了一個類似的問題在Python中實現。

鏈接： Replacing a sublist with another sublist in python

什麼建議嗎？謝謝。

Answer 1

type 'a strip_result = 
| No_match 
| Too_short 
| Tail of 'a list 

(** [try_strip li subli] tries to 
    remove the prefix [subli] from the list [li] *) 
let rec try_strip li subli = match li, subli with 
    | _, [] -> Tail li 
    | [], _ -> Too_short 
    | hli::tli, hsub::tsub -> 
    if hli <> hsub then No_match 
    else try_strip tli tsub 

let rec replace_sublist li from_sub to_sub = 
    match li with 
    | [] -> [] 
    | head::tail -> 
     match try_strip li from_sub with 
     | Too_short -> li 
     | No_match -> head :: replace_sublist tail from_sub to_sub 
     | Tail rest -> to_sub @ replace_sublist rest from_sub to_sub 

let test = 
    (* simple replace *) 
    assert (replace_sublist [1;2;3;4] [2;3] [-2;-3] = [1;-2;-3;4]); 
    (* multiple replace *) 
    assert (replace_sublist [1;2;3;2;4] [2] [0] = [1;0;3;0;4]); 
    (* stop while partial match *) 
    assert (replace_sublist [1;2;3;4] [3;4;5] [0] = [1;2;3;4]); 
    (* stop at match *) 
    assert (replace_sublist [1;2;3;4] [3;4] [2;1] = [1;2;2;1]); 
    (* tricky repeating sublist case *) 
    assert (replace_sublist [2;2;3] [2;3] [0] = [2;0]); 
() 


(* tail-rec version: instead of concatenating elements before 
    the recursive call 
    head :: replace_sublist ... 
    to_sub @ replace_sublist ... 
    keep an accumulator parameter `acc` to store the partial result, 
    in reverse order 
    replace (t :: acc) ... 
    replace (List.rev_append to_sub acc) ... 
*) 
let replace_sublist li from_sub to_sub = 
    let rec replace acc li = match li with 
    | [] -> List.rev acc 
    | head::tail as li -> 
     match try_strip li from_sub with 
     | Too_short -> List.rev (List.rev_append li acc) 
     | No_match -> replace (head :: acc) tail 
     | Tail rest -> replace (List.rev_append to_sub acc) rest 
    in replace [] li 

PS：這是衆所周知的移動，該算法可以得到改善，後try_strip失敗，不只是下一個元素在列表中，但由我們知道的一些元素不能開始新的匹配。然而，跳過的元素數量並不像List.length from_sub - 1那樣簡單，它需要從模式結構中預先計算（這取決於「棘手的重複次級列表」的存在）。這是Knuth-Morris-Pratt算法。

Answer 2

你可以做這樣的事情：

let replace listo lista listb = 
    let rec loop listo lista listb accu = 
    match listo with 
     [] -> List.rev accu 
    | x :: xs -> 
     if xs = lista then List.rev_append (x :: accu) listb 
     else loop xs lista listb (x :: accu) in 
    loop listo lista listb [] 

首先，你需要找到的子列表lista。一旦你找到這個列表，你可以恢復蓄電池accu，然後追加listb

Answer 3

這實質上是一個子串搜索和替換。如果您的列表很長，您可能需要使用像Knuth-Morris-Pratt這樣的花式算法來避免比較的二次數。

（我會寫一些代碼，錯誤gasche已經做了出色的工作。）