F# removing the first occurrence of an element in a list

user_19260704 0
Viewed 65

I want to remove the first occurrence of a given element in a list that has possible duplicates. For example, a list with [1; 6; 1]. I only want to remove 1 once and returns the list [6;1]. My current implementation:

let rec remove l x =
        match l with
        | [] -> []
        | h::t when h = x -> t
        | h::t -> h::(remove l h)

this works only for lists that the number I am trying to remove is the first element. For a list like [6; 7; 6] if I wanted to remove the number 7 and return [6; 6]. It does not traverse the list and remove 7 with my current implementation. What can I do to traverse the entire list and remove only the first occurrence of an element?

f#
3 Answers

The issue you have is in the last line of your code

let rec remove l x =
     match l with
     | [] -> []
     | h::t when h = x -> t
     | h::t -> h::(remove l h)
                   ^^^^^^^^^^^

  1. You want to keep the head h and process the tail t but the code do not do this, referring to h and l, instead of t and x.

  2. The type signature of remove is correctly inferred to 'a list-> 'a -> 'a list but the wrong second argument is used in the last match branch. It is using h rather than x as the element to remove parameter.

  3. The first argument is also incorrect, since referring to l does not change through each recursion. It needs to refer to the latest tail t.

So the last match branch should read:

| h::t -> h::(remove t x)

Here is the full corrected code;

let rec remove l x =
    match l with
    | [] -> []
    | h::t when h = x -> t
    | h::t -> h::(remove t x)
user_4238900

I ended up writing the same code you did and it seems to work just fine. I reordered the parameters for better piping. I could also work to make this tail-recursive.

let rec removeFirst elem xs =
    match xs with
    | [] -> []
    | h :: t when elem = h -> t
    | h :: t -> h :: (removeFirst elem t)

> removeFirst 2 [1;2;2;1];;
val it: int list = [1; 2; 1]
user_149686530

Tail-call optimized version

let removeFirst elem list =
    let rec loop head tail =
        match tail with
        | [] -> list
        | x :: xs when x = elem -> (List.rev head) @ xs
        | x :: xs -> loop (x::head) xs
    loop [] list

removeFirst 1 [1; 2; 3] |> printfn "%A" // [2; 3]
removeFirst 2 [1; 2; 3] |> printfn "%A" // [1; 3]
removeFirst 3 [1; 2; 3] |> printfn "%A" // [1; 2]
removeFirst 4 [1; 2; 3] |> printfn "%A" // [1; 2; 3]

How it works:

We're traversing list keeping visited elements in head and unvisited in tail. Take first element from tail and see if it's equal to elem we're searching for. If element is found, reverse head and attach to tail without removed element. If element is not found, attach current to head and continue. If we've reached end of list and element isn't found, then return list without modifications.

Example:

Given list of [1; 2; 3; 4; 5] and element 3 iterations will look like this:

head tail x xs
[] [1; 2; 3; 4; 5] 1 [2; 3; 4; 5]
[1] [2; 3; 4; 5] 2 [3; 4; 5]
[2; 1] [3; 4; 5] 3 [4; 5]

At last iteration element is found and all that's remains is to build list: reverse of [2; 1] is [1; 2], attach to [4; 5] and get [1; 2; 4; 5].

Note: head is kept in reverse to improve performance of building it from O(n2) to O(n). Combining head with xs in second branch can be improved from O(head.length*2) to O(head.length) by avoiding usage of rev with @ and building result list manually

user_103396750
Related