F# 从列表中插入/删除项目 [英] F# insert/remove item from list

问题描述

我应该如何从列表中删除给定的元素?例如，假设我有列表 ['A';'乙';'C';'D';'E'] 并且想要删除索引 2 处的元素以生成列表 ['A';'乙';'D';'E']?我已经编写了以下代码来完成任务，但是当我已经知道索引时，遍历列表的开头似乎效率很低.

让删除 lst i =让 rec 删除 lst lst' =匹配 lst 与|[] ->最后'|h::t ->如果 List.length lst = i 那么lst'@t别的删除 t (lst' @ [h])删除 lst []让 myList = ['A';'乙';'C';'D';'E']让 newList = 删除 myList 2

或者，我应该如何在给定位置插入元素?我的代码与上述方法类似，而且很可能效率也很低.

让插入 lst i x =让 rec 插入 lst lst' =匹配 lst 与|[] ->最后'|h::t ->如果 List.length lst = i 那么lst' @ [x] @ lst别的插入 t (lst' @ [h])插入 lst []让 myList = ['A';'乙';'D';'E']让 newList = 插入 myList 2 'C'

解决方案

似乎是最惯用的(不是尾递归):

let rec 插入 v i l =匹配我，我|0, xs ->v::xs|我，x::xs ->x::插入 v (i - 1) xs|我，[] ->失败索引超出范围"让 rec 删除 i l =匹配我，我|0, x::xs ->xs|我，x::xs ->x::remove (i - 1) xs|我，[] ->失败索引超出范围"

<块引用>

看起来效率很低当我遍历列表的开头已经知道索引了.

F# 列表是单链表，因此您无法对它们进行索引访问.但大多数时候，你不需要它.数组上的大多数索引操作都是从前到尾的迭代，这正是不可变列表上最常见的操作.将项添加到数组的末尾也很常见，这实际上并不是单向链表上最有效的操作，但大多数时候您可以使用cons and reverse"习语或使用不可变队列来获取相同的结果.

如果您需要索引访问，Arrays 和 ResizeArrays 确实是最佳选择，但它们不是一成不变的.少数不可变数据结构(如 VList)允许您创建类似列表的数据结构，如果您确实需要，它支持 O(1) 缺点和 O(log n) 索引随机访问.

How should I go about removing a given element from a list? As an example, say I have list ['A'; 'B'; 'C'; 'D'; 'E'] and want to remove the element at index 2 to produce the list ['A'; 'B'; 'D'; 'E']? I've already written the following code which accomplishes the task, but it seems rather inefficient to traverse the start of the list when I already know the index.

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

Alternatively, how should I insert an element at a given position? My code is similar to the above approach and most likely inefficient as well.

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'

解决方案

Seems the most idiomatic (not tail recursive):

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"

it seems rather inefficient to traverse the start of the list when I already know the index.

F# lists are singly-linked lists, so you don't have indexed access to them. But most of the time, you don't need it. The majority of indexed operations on arrays are iteration from front to end, which is exactly the most common operation on immutable lists. Its also pretty common to add items to the end of an array, which isn't really the most efficient operation on singly linked lists, but most of the time you can use the "cons and reverse" idiom or use an immutable queue to get the same result.

Arrays and ResizeArrays are really the best choice if you need indexed access, but they aren't immutable. A handful of immutable data structures like VLists allow you to create list-like data structures supporting O(1) cons and O(log n) indexed random access if you really need it.

这篇关于F# 从列表中插入/删除项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！