Замена подсписка другим подсписком в Ocaml

Question

Я хочу заменить подсписок lista с другим подсписком listb из списка listo добиться следующего результата:

let replace_sublist listo lista listb = 

В листе, если есть подсписок = lista, то замените этот подсписок списком.

Я нашел аналогичный вопрос, реализованный в Python.

Ссылка: замена подсписка другим подсписком в 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, он должен быть предварительно вычислен из структуры шаблона (это зависит от наличия "хитрых повторяющихся подсписков"). Это алгоритм Кнута-Морриса-Пратта.

Answer 2

По сути это поиск и замена подстроки. Если ваши списки длинные, вы можете использовать причудливый алгоритм, такой как Кнут-Моррис-Пратт, чтобы избежать квадратичного числа сравнений.

(Я собирался написать некоторый код, ошибка Gasche уже сделала отличную работу.)

Answer 3

Вы можете сделать что-то подобное:

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