F＃从列表中插入/删除项目

一尘不染

F＃从列表中插入/删除项目

algorithm

我应该如何从列表中删除给定的元素？例如，假设我有列表，['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'

阅读 173

2020-07-28

共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＃列表是单链接列表，因此您没有索引访问它们。但是大多数时候，您不需要它。数组上的大多数索引操作都是从头到尾的迭代，这恰恰是不可变列表上最常见的操作。将项目添加到数组的末尾也很常见，这并不是单链列表上最有效的操作，但是大多数时候，您可以使用“
cons and reverse”惯用法或使用不可变队列来获取同样的结果。

如果您需要索引访问，则数组和ResizeArrays确实是最佳选择，但它们并非一成不变。少数不可变的数据结构（例如VLists）允许您创建确实支持O（1）缺点和O（log
n）索引随机访问的类似列表的数据结构。

2020-07-28