1

I want to replace a sublist lista with another sublist listb from a list listo to achieve the following result:

let replace_sublist listo lista listb =

In listo , if there is a sublist = lista, then replace this sublist with listb.

I found a similar question implemented in python.

Link: Replacing a sublist with another sublist in python

Any suggestion? Thanks.

Community
  • 1
  • 1
Robin
  • 134
  • 9

3 Answers3

2
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: it is well-known that this algorithm can be improved by moving, after try_strip failed, not just to the next element in the list but by some number of elements that we know cannot start a new match. However, this number of elements to jump over is not something simple like List.length from_sub - 1, it needs to be precomputed from the pattern structure (it depends from the presence of "tricky repeating sublists"). This is the Knuth-Morris-Pratt algorithm.

gasche
  • 31,259
  • 3
  • 78
  • 100
1

You can do something like that :

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 []

First you need to find the sublist lista. Once you find this list, you can just revert the accumulator accu and then append the listb

Çağdaş Bozman
  • 2,537
  • 16
  • 21
  • your inner `loop` function does not need to take `lista` and `listb` as parameters, as they do not change during `listo` traversal. – Virgile Mar 15 '13 at 12:01
  • also, this isn't quite what is described in the link provided by the original poster, where `lista` can be in the middle of `listo`, not necessarily at the end. – Virgile Mar 15 '13 at 12:06
  • By passing `lista` and `listb`, we just avoid closure allocation here as there is no more free variables. – Çağdaş Bozman Mar 15 '13 at 14:12
  • This kind of "degrading code readability over imaginary performance benefits" is best avoided when showing code to beginners. On my machine, removing those two useless parameters makes the code 10-15% faster on lists of size 10_000, with varying speedup (sometimes none) on other list sizes (seems related to when the GC kicks in; I don't care about the details, I'll just use the readable code). – gasche Mar 15 '13 at 15:19
  • I also think this solution just consider that lista is the tail for listo. It doesn't work for the case like : `replace [1;2;3;4;5][2;3][1;1;1] ` , this solution gives the result `int list = [1; 2; 3; 4; 5]` – Robin Mar 15 '13 at 18:51
1

This is essentially a substring search and replace. If your lists are long, you might want to use a fancy algorithm like Knuth-Morris-Pratt to avoid a quadratic number of comparisons.

(I was going to write some code, bug gasche already did an excellent job.)

Jeffrey Scofield
  • 65,646
  • 2
  • 72
  • 108