Remove element from list in f#

Question

Suppose I have a sorted list l, with possible duplicate values - and I want to return a list with the value n removed from l, but only once. - eg for inputs [1,2,3,3,3,4] and 3, return [1,2,3,3,4]. How would I do this?

You mean a `System.Collections.Generic.SortedList` ? Or an (assumed sorted) immutable F# list? — Gus, Jan 27 '15 at 22:21
immutable F# list. I edited the question to make this clearer — Dr. John A Zoidberg, Jan 27 '15 at 22:50
It's still unclear what you are asking - the current wording suggests that you want a function that takes a list `l` and a value `n`, removes value `n` from the list and returns all the other elements of `l` (including potential duplicates of `n`) as an array. Is this what you want? — scrwtp, Jan 27 '15 at 23:44
Yes, I've improved the clarity of the question to reflect this. the output should actually be a list (I put array by accident, sorry) — Dr. John A Zoidberg, Jan 28 '15 at 00:17

score 6 · Accepted Answer · answered Jan 28 '15 at 00:27

6

The most straightforward approach would be something like this:

let rec remove n lst = 
    match lst with
    | h::tl when h = n -> tl
    | h::tl -> h :: (remove n tl)
    | []    -> []

You recursively traverse the list until you find n - if you do, you drop it and return the tail. Note that this isn't tail-recursive, but can be easily made so.

answered Jan 28 '15 at 00:27

scrwtp

13,437
2
26
30

You could easily use list.fold where accumulator is simple bool. This would make it tail recursive – MichalMa Jan 28 '15 at 15:27
@MichalMa: You mean a fold where the accumulator is the output list + the bool flag? That would work, but with fold you would have to traverse the list to the end, which is not necessary. By a simple change I meant introducing an inner function with an accumulator for building the list. – scrwtp Jan 28 '15 at 16:52

score 1 · Answer 2 · edited May 23 '17 at 12:26

1

For those interested (I know I was), I came up with a tail-optimized version of the accepted answer using an accumulator since I am new to F# and very rusty with my recursion work.

let remove n list =
    let rec removeTail n list acc =
        match list with
        | h::tl when h = n -> List.append (List.rev acc) tl
        | h::tl -> (removeTail n tl (h::acc))
        | [] -> List.rev acc
    removeTail n list []

Resources I used:

edited May 23 '17 at 12:26

Community

1
1

answered Jan 28 '15 at 19:36

Sven Grosen

5,616
3
30
52

Looks good, but you want to return the reversed `acc` in empty list case as well. – scrwtp Jan 28 '15 at 19:48
@scrwtp thanks, and thanks for the original answer too – Sven Grosen Jan 28 '15 at 20:01

score -1 · Answer 3 · answered Jan 28 '15 at 00:50

Before List.distinct is available, you can use Seq.distinct :

let l = [1;1;2;3;3;3;4]
let dl = 
    l
    |> Seq.ofList
    |> Seq.distinct
    |> Seq.toList

In F# 4.0, we will have List.distinct as announced here :

In F# 4.0, the collections API has been fully normalized across Array, List, and Seq. There are now dedicated, optimized implementations of all common operations for each type, and even a few brand-new functions. This represents the addition of a whopping 95 APIs in total.

This is *not* what the OP was looking for. – scrwtp Jan 28 '15 at 19:49 — scrwtp, Jan 28 '15 at 19:49

Remove element from list in f#

3 Answers3