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'
3 ответа
Кажется наиболее идиоматическим (не хвостовым рекурсивным):
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) индексированный произвольный доступ, если вам это действительно нужно.
Если вам нужен произвольный доступ в списке, рассмотрите возможность использования System.Collections.Generic.List или System.Collections.Generic.LinkedList вместо списка F#.
Удаление элемента по указанному индексу не является типичной операцией в функциональном программировании - вот почему кажется трудным найти правильную реализацию этих операций. В функциональном программировании вы обычно обрабатываете список элемент за элементом, используя рекурсию, или реализуете обработку в терминах декларативных операций более высокого уровня. Возможно, если вы уточните, какова ваша мотивация, мы сможем дать лучший ответ.
В любом случае, для реализации двух операций, которые вы хотели, вы можете использовать существующие функции более высокого порядка (которые обходят весь список несколько раз, потому что нет хорошего способа сделать это без обхода списка):
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
Однако, как было отмечено ранее - если у вас нет очень веских причин для использования этих функций, вам, вероятно, следует описать свои цели более широко и использовать альтернативное (более функциональное) решение.