Take the 2-minute tour ×

I have a sorted sequence and want to go through it and return the unique entries in the sequence. I can do it using the following function, but it uses reference variables and I don't think it's the correct way of solving the problem.

    let takeFirstCell sectors = 
        let currentRNCId = ref -1
        let currentCellId = ref -1
        seq {
            for sector in sectors do
                if sector.RNCId <> !currentRNCId || sector.CellId <> !currentCellId then
                    currentRNCId := sector.RNCId
                    currentCellId := sector.CellId
                    yield sector

How can I do this in a functional way?

share|improve this question

6 Answers 6

up vote 4 down vote accepted
|> Seq.distinctBy id
|> printfn "%A"
share|improve this answer
Doh - how could I miss that - thanks! –  Nick Randell Jul 27 '11 at 10:09

Seq.distinct (1::[1..5]) returns seq [1; 2; 3; 4; 5]. Is that what you meant?

share|improve this answer

Just initialize a unique collection (like a set) with the sequence like this:

set [1; 2; 3; 3; 4; 5; 5];;
=> val it : Set<int> = set [1; 2; 3; 4; 5]
share|improve this answer

distinct and distinctBy both use Dictionary and therefore require hashing and a bit of memory for storing unique items. If your sequence is already sorted, you can use the following approach (similar to yours). It's nearly twice as fast and has constant memory use, making it usable for sequences of any size.

let distinctWithoutHash (items:seq<_>) =
  seq {
    use e = items.GetEnumerator()
    if e.MoveNext() then
      let prev = ref e.Current
      yield !prev
      while e.MoveNext() do
        if e.Current <> !prev then 
          yield e.Current
          prev := e.Current

let items = Seq.init 1000000 (fun i -> i / 2)
let test f = items |> f |> (Seq.length >> printfn "%d")

test Seq.distinct        //Real: 00:00:01.038, CPU: 00:00:01.435, GC gen0: 47, gen1: 1, gen2: 1
test distinctWithoutHash //Real: 00:00:00.622, CPU: 00:00:00.624, GC gen0: 44, gen1: 0, gen2: 0

I couldn't figure out a way to use mutables instead of refs (short of hand-coding an enumerator), which I'm sure would speed it up considerably (I tried it--it makes no difference).

share|improve this answer
mutables aren't allowed to escape their environment (placed on the heap to be referenced by a closure) and since computation expressions like seq (well, seq gets some special compiler optimizations) desugar to a chain of continuations, you must use ref (the F# designers wanted us to be able to reason about mutables as purely local). –  Stephen Swensen Jul 27 '11 at 16:38
... so I think even if mutables were allowed to escape their environment, they would probably not give a performance increase since likely they'd be allocated on the heap (though another possible implementation is just to keep the stackframe alive after returning). –  Stephen Swensen Jul 27 '11 at 16:41
Oh, and regarding your distinctWithoutHash implementation, another nice thing about it is that it is lazy! –  Stephen Swensen Jul 27 '11 at 16:51
@Stephen: I wrote an IEnumerator<_> that used mutable instead, but I won't bother posting it--the performance was (surprisingly) almost the same. –  Daniel Jul 27 '11 at 21:10

The solution below, preserves order of elements and returns only the first occurance of an element in a generic list. Of course this generates a new List with the reduandant items removed.

// ** Return a list with subsequent redundant elements removed

let removeDuplicates(lst : 'a list) = 
    let f item acc =
        match acc with 
        | [] -> [item]
        | _ ->
            match List.exists(fun x -> x = item) acc with
            | false -> item :: acc
            | true -> acc
    |> List.rev
    |> fun x -> List.foldBack f x []
    |> List.rev

// ** END OF FUNCTION removeDuplicates

val removeDuplicates : 'a list -> 'a list when 'a : equality
val testList : int list = [1; 4; 3; 1; 2; 2; 1; 1; 3; 4; 3]
val tryAbove : int list = [1; 4; 3; 2]
share|improve this answer
dont match true/false just use if –  Guillaume Massé Apr 8 at 13:16

In my case I could not use Seq.distinct because I needed to preserve order of list elements. I used solution from http://ocaml.org/learn/tutorials/99problems.html. I think it is quite short

let rec compress = function
    | a :: (b :: _ as t) -> if a = b then compress t else a :: compress t
    | smaller -> smaller
share|improve this answer

Your Answer


