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#列表是单链接列表,因此您没有索引访问它们.但大多数时候,你不需要它.数组上的大多数索引操作都是从前到后的迭代,这正是不可变列表上最常见的操作.将项添加到数组的末尾也很常见,这对于单链表并不是最有效的操作,但大多数时候你可以使用"缺点和反向"成语或使用不可变队列来获取同样的结果.

如果您需要索引访问,Arrays和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.filter (fun (i, _) -> i <> index) |> List.map snd

在List.Indexed返回的元组这是在列表中的索引，并在该位置的实际项目之后，所有它需要的是过滤一个元组匹配输入的指标，后来得到实际的项目清单。

我希望这可以帮助那些不太关心效率并想要简短代码的人