F# insert/remove item from list

Question

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'

Solution 1

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.

Solution 2

Removing element at the specified index isn't a typical operation in functional programming - that's why it seems difficult to find the right implementation of these operations. In functional programming, you'll usually process the list element-by-element using recursion, or implement the processing in terms of higher-level declarative operations. Perhaps if you could clarfiy what is your motivation, we can give a better answer.

Anyway, to implement the two operations you wanted, you can use existing higher-order functions (that traverse the entire list a few times, because there is really no good way of doing this without traversing the list):

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

To insert element to the specified index, you could write:

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

However, as noted earlier - unless you have a very good reasons for using these functions, you should probably consider describing your goals more broadly and use an alternative (more functional) solution.

Solution 3

If you need random access in a list, consider using System.Collections.Generic.List<T> or System.Collections.Generic.LinkedList<T> instead of a F# list.

Solution 4

I know this has been here for a while now, but just had to do something like this recently and I came up with this solution, maybe it isn't the most efficient, but it surely is the shortest idiomatic code I found for it

let removeAt index list =
    list |> List.indexed |> List.filter (fun (i, _) -> i <> index) |> List.map snd

The List.Indexed returns a list of tuples which are the index in the list and the actual item in that position after that all it takes is to filter the one tuple matching the inputted index and get the actual item afterwards.

I hope this helps someone who's not extremely concerned with efficiency and wants brief code

Solution 5

The following includes a bit of error checking as well

let removeAt index = function
| xs when index >= 0 && index < List.length xs -> 
      xs
      |> List.splitAt index
      |> fun (x,y) -> y |> List.skip 1 |>  List.append x
| ys -> ys

Lets go thru it and explain the code

// use the function syntax
let removeAt index = function
// then check if index is within the size of the list
| xs when index >= 0 && index < List.length xs -> 
      xs
      // split the list before the given index
      // splitAt : int -> 'T list -> ('T list * 'T list)
      // this gives us a tuple of the the list with 2 sublists
      |> List.splitAt index
      // define a function which
      // first drops the element on the snd tuple element
      // then appends the remainder of that sublist to the fst tuple element
      // and return all of it
      |> fun (x,y) -> y |> List.skip 1 |>  List.append x
      //index out of range so return the original list
| ys -> ys

And if you don't like the idea of simply returning the original list on indexOutOfRange - wrap the return into something

let removeAt index = function
| xs when index >= 0 && index < List.length xs -> 
      xs
      |> List.splitAt index
      |> fun (x,y) -> y |> List.skip 1 |>  List.append x
      |> Some
| ys -> None

I think this should be quite faster than Juliet's or Tomas' proposal but most certainly Mauricio's comment is hitting it home. If one needs to remove or delete items other data structures seem a better fit.

View more solutions