F # вставить/удалить элемент из списка

Как мне сделать удаление данного элемента из списка? В качестве примера, скажем, у меня есть список ['A'; 'B'; 'C'; 'D'; 'E'] и вы хотите удалить элемент в индексе 2, чтобы создать список ['A'; 'B'; 'D'; 'E']? Я уже написал следующий код, который выполняет задачу, но мне кажется неэффективным прохождение начала списка, когда я уже знаю индекс.

let remove lst i =
    let rec remove lst lst' =
        match lst with
        | []   -> lst'
        | h::t -> if List.length lst = i then
                      lst' @ t
                  else
                      remove t (lst' @ [h])
    remove lst []

let myList = ['A'; 'B'; 'C'; 'D'; 'E']
let newList = remove myList 2

В качестве альтернативы, как мне вставить элемент в заданную позицию? Мой код аналогичен приведенному выше подходу и, скорее всего, неэффективен.

let insert lst i x =
    let rec insert lst lst' =
        match lst with
        | []   -> lst'
        | h::t -> if List.length lst = i then
                      lst' @ [x] @ lst
                  else
                      insert t (lst' @ [h])
    insert lst []

let myList = ['A'; 'B'; 'D'; 'E']
let newList = insert myList 2 'C'

Ответ 1

Кажется, самый идиоматический (не хвостовой рекурсивный):

let rec insert v i l =
    match i, l with
    | 0, xs -> v::xs
    | i, x::xs -> x::insert v (i - 1) xs
    | i, [] -> failwith "index out of range"

let rec remove i l =
    match i, l with
    | 0, x::xs -> xs
    | i, x::xs -> x::remove (i - 1) xs
    | i, [] -> failwith "index out of range"

представляется довольно неэффективным перейдите в начало списка, когда я уже знаете индекс.

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

Массивы и ResizeArrays - действительно лучший выбор, если вам нужен индексированный доступ, но они не являются неизменными. Несколько неизменных структур данных, таких как VLists, позволяют создавать структуры, похожие на список, поддерживающие O (1) минусы и O (log n) индексированный произвольный доступ, если вам это действительно нужно.

Ответ 2

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

В любом случае, чтобы реализовать две операции, которые вы хотели, вы можете использовать существующие функции более высокого порядка (которые пересекают весь список несколько раз, потому что на самом деле нет хорошего способа сделать это без прохождения списка):

let removeAt index input =
  input 
  // Associate each element with a boolean flag specifying whether 
  // we want to keep the element in the resulting list
  |> List.mapi (fun i el -> (i <> index, el)) 
  // Remove elements for which the flag is 'false' and drop the flags
  |> List.filter fst |> List.map snd

Чтобы вставить элемент в указанный индекс, вы можете написать:

let insertAt index newEl input =
  // For each element, we generate a list of elements that should
  // replace the original one - either singleton list or two elements
  // for the specified index
  input |> List.mapi (fun i el -> if i = index then [newEl; el] else [el])
        |> List.concat

Однако, как отмечалось ранее, если у вас нет очень веских оснований для использования этих функций, вам, вероятно, следует рассмотреть более подробное описание ваших целей и использовать альтернативное (более функциональное) решение.

Ответ 3

Если вам нужен произвольный доступ в списке, используйте System.Collections.Generic.List<T> или System.Collections.Generic.LinkedList<T> вместо списка F #.

Ответ 4

Ниже приведена также проверка ошибок

let removeAt index = function
| xs when index >= 0 && index < List.length xs -> 
      xs
      |> List.splitAt index
      |> fun (x,y) -> y |> List.skip 1 |>  List.append x
| ys -> ys

Давайте рассмотрим его и объясним код

// use the function syntax
let removeAt index = function
// then check if index is within the size of the list
| xs when index >= 0 && index < List.length xs -> 
      xs
      // split the list before the given index
      // splitAt : int -> 'T list -> ('T list * 'T list)
      // this gives us a tuple of the the list with 2 sublists
      |> List.splitAt index
      // define a function which
      // first drops the element on the snd tuple element
      // then appends the remainder of that sublist to the fst tuple element
      // and return all of it
      |> fun (x,y) -> y |> List.skip 1 |>  List.append x
      //index out of range so return the original list
| ys -> ys

И если вам не нравится идея просто вернуть исходный список на indexOutOfRange - оберните возврат во что-то

let removeAt index = function
| xs when index >= 0 && index < List.length xs -> 
      xs
      |> List.splitAt index
      |> fun (x,y) -> y |> List.skip 1 |>  List.append x
      |> Some
| ys -> None

Я думаю, что это должно быть довольно быстро, чем предложение Джульетты или Томаса, но, скорее всего, комментарий Маурицио поражает его. Если нужно удалить или удалить элементы, то другие структуры данных лучше подходят.

Ответ 5

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

let removeAt index list =
    list |> List.indexed |> List.filer (fun (i, _) -> i <> index) |> List.map snd

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

Я надеюсь, что это поможет кому-то, кто не очень озабочен эффективностью и хочет получить короткий код