функция библиотеки для установки n-го элемента списка

Question

Есть ли библиотечная функция для выполнения чего-то вроде этого set_elem объявления?

set_elem (l : int list) (i : int) (x : int) : int list

Например:

(set_elem [1; 2; 3; 4] 1 90)

вернет:

[1; 90; 3; 4]

Answer 1

Другие решения запускаются за O(n) время (где n - длина списка), когда вам действительно нужно, чтобы ваше решение работало только за O(i) время (где i - ваш индекс).

Вот эффективная хвостовая рекурсивная функция:

let set l ~i ~data =
  let rec helper ~prev_rev ~curr ~i =
    match curr, i with
    | []        , _ -> List.rev prev_rev
    | _  :: curr, 0 -> List.rev_append prev_rev (data :: curr)
    | hd :: curr, _ -> helper ~prev_rev:(hd :: prev_rev) ~curr ~i:(i - 1)
  in
  if i < 0 || i >= List.length l
  then l
  else helper ~prev_rev:[] ~curr:l ~i

Эта функция не изменит l, если вы передадите неверный индекс.Вы можете изменить это, чтобы вызвать исключение, если хотите.

Answer 2

В качестве альтернативы, если вы хотите использовать изменяемую структуру данных, модуль Array может сделать именно это.

let a = [|1; 2; 3; 4|];;
(* val a : int array = [|1; 2; 3; 4|] *)

Array.set a 1 90;;
(* - : unit = () *)

a;;
(* - : int array = [|1; 90; 3; 4|] *)

Answer 3

Нет, и это, скорее всего, потому, что прямая индексация - довольно плохой вариант использования для неизменяемого связанного списка с затратами, которые должным образом не отражаются такими вспомогательными функциями.Если вы обнаружите, что делаете это часто, вам следует рассмотреть возможность использования массива.

Тем не менее, самый простой способ, который я могу придумать, - это использовать List.mapi для возврата нового элемента, только если мы находимся направильный индекс и существующий элемент в противном случае:

List.mapi (fun i el -> if i = 1 then x else el) l

Или как функция с желаемой подписью:

let set_elem (l : int list) (i : int) (x : int) : int list =
  List.mapi (fun i' el -> if i = i' then x else el) l

Answer 4

Нет, в стандартной библиотеке List нет библиотечной функции, но не так уж сложно ее кодировать.

Вот нерекурсивная реализация.

(** [insert n el lst] inserts element [el] in the [n]th position in the 
    list [lst].
    Raises: [Failure] if index is out of bounds *)
let rec insert n el lst =
  match n,lst with 
  | i, _ when i >= List.length lst -> failwith "Index out of Bounds"
  | _, [] -> []
  | 0, _::t -> el::(insert (-1) el t)
  | i, h::t -> h::(insert (i-1) el t)

Идея состоит в том, чтобы сопоставить образцы с n и lst вместе.

Если вы нажмете пустой список, верните начальное значение (или аккумулятор, если вы хотите получить хвостовое рекурсивное решение).

Если n достигнет 0, добавьте элемент в списоки продолжайте просматривать остальную часть списка, чтобы сохранить другие элементы (но убедитесь, что вы никогда не нажмете снова 0, поэтому я использовал -1).

В противном случае вы добавляете старые элементысписок, пока n не достигнет 0.