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

Question

Как мне следует удалить данный элемент из списка? Например, скажем, у меня есть список ['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'

Answer 1

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

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

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

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

Answer 2

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

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) cons и O (log n), индексированный произвольный доступ, если он вам действительно нужен.

Answer 3

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

Answer 4

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

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

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

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

Answer 5

Следующее включает в себя также немного проверки ошибок

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

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