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已经做了出色的工作。）