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

问题描述

我应该如何去从列表中删除一个给定的元素？举个例子，说我有列表 ['A'; B; 'C'; 'D'; 'E'] 和要删除的元素的索引2，产生列表 ['A'; B; 'D'; 'E'] ？我已经写了下面的code的完成了任务，但似乎相当低效遍历列表的开始时，我已经知道了索引。

 让我们删除LST I =
    让REC删除LST LST =
        比赛LST与
        | []  - ＆GT;乐善堂
        | ^ h ::笔 - ＆GT;如果List.length LST =我则
                      乐善堂@ T
                  其他
                      除去叔（LST'@ [H]）
    删除LST []

让myList上='A'; B; 'C'; 'D'; 'E']
让newList =删除myList中2
 

另外，我应该怎么插在指定位置的元素？我的code是与上述类似的方法，最有可能低效以及

 让插入LST我X =
    让REC插入LST LST =
        比赛LST与
        | []  - ＆GT;乐善堂
        | ^ h ::笔 - ＆GT;如果List.length LST =我则
                      乐善堂@ [X] // @ LST
                  其他
                      插入T（LST'@ [H]）
    插入LST []

让myList上='A'; B; 'D'; 'E']
让newList =插入myList上2'C'
 

解决方案

似乎是最地道的（不是尾递归）：

 让REC插入V I L =
    赛我，带L
    | 0，XS  - ＆GT; v :: XS
    | I，X :: XS  - ＆GT; X ::插入V（I  -  1）XS
    |我，[]  - ＆GT; failwith索引超出范围

让拍摄消除I L =
    赛我，带L
    | 0，X :: XS  - ＆GT; XS
    | I，X :: XS  - ＆GT; X ::删除（I  -  1）XS
    |我，[]  - ＆GT; failwith索引超出范围
 

  

这似乎相当低效   遍历列表的开始，当我   已经知道索引

F＃列表是单链表，所以你没有索引访问它们。但大多数时候，你并不需要它。大多数对数组索引操作都是由前结束，这也正是在不可改变列出了最常见的操作迭代。它也pretty的共同项目添加到一个数组，这是不是真的对单链表的最有效的操作结束，但大部分的时间，你可以使用缺点和反向成语或使用不可变排队以获得相同的结果。

数组和ResizeArrays真的是最好的选择，如果你需要索引访问，但它们并非一成不变。少数不可变的数据结构一样VLists允许您创建支持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屋！