F#: removing duplicates from a seq is slow

The problem is with how you use sequences. All those yields, heads and tails are spinning a web of iterators branching off of iterators, and when you finally materialize it when you call List.ofSeq, you're iterating through your input sequence way more than you should.

Each of those Seq.heads is not simply taking the first element of a sequence - it's taking the first element of the tail of a sequence of a tail of a sequence of tail of a sequence and so on.

Check this out - it'll count the times the element constructor is called:

let count = ref 0

Seq.init 1000 (fun i -> count := !count + 1; 1) 
|> dedupeTakingLast (fun (x,y) -> x = y) None 
|> List.ofSeq

Incidentally, just switching out all the Seqs to Lists makes it go instantly.

The performance issue comes from the nested calls to Seq.tail. Here's the source code to Seq.tail

[<CompiledName("Tail")>]
let tail (source: seq<'T>) =
    checkNonNull "source" source
    seq { use e = source.GetEnumerator() 
          if not (e.MoveNext()) then 
              invalidArg "source" (SR.GetString(SR.notEnoughElements))
          while e.MoveNext() do
              yield e.Current }

If you call Seq.tail(Seq.tail(Seq.tail(...))) the compiler has no way of optimizing out the enumerators that are created by GetEnumerator(). Subsequent returned elements have to go through every nested sequence and enumerator. This results in every returned element having to bubble up through all previously created sequences and all of these sequences have to increment their internal state as well. The net result is a running time of O(n^2) instead of linear O(n).

Unfortunately there is currently no way to represent this in a functional style in F#. You can with a list (x::xs) but not for a sequence. Until the language gets better native support for sequences, don't use Seq.tail in recursive functions.

Using a single enumerator will fix the performance problem.

let RemoveDuplicatesKeepLast equals (items:seq<_>) =
    seq {
        use e = items.GetEnumerator()

        if e.MoveNext() then
            let mutable previous = e.Current

            while e.MoveNext() do
                if not (previous |> equals e.Current) then 
                    yield previous
                previous <- e.Current

            yield previous
    }

let test = [("a", 1); ("b", 2); ("b", 3); ("b", 4); ("c", 5)]
let FirstEqual a b = fst a = fst b

RemoveDuplicatesKeepLast FirstEqual test
|> printf "%A"

// output
// seq [("a", 1); ("b", 4); ("c", 5)]

The first version of this answer has a recursive version of the above code without mutation.

Seq.isEmpty, Seq.head and Seq.tail are slow because they all create a new Enumerator instance which it then calls into. You end up with a lot of GC.

Generally, Sequences are forward only, and if you use them 'like pattern matching for lists', the performance becomes really shoddy.

Looking a bit at your code... | None -> yield! s creates a new Enumerator even though we know s is empty. Every recursive call probably ends up creating a new IEnumerable that is then directly turned into an Enumerator from the call-site with yield!.