Я пытаюсь написать функцию, которая отсеивает последовательные дубликаты, как определено данной функцией равенства, изseq<'a> но с изюминкой: мне нужнопрошлой дубликат из серии дубликатов, чтобы превратить его в результирующую последовательность. Например, если у меня есть последовательность[("a", 1); ("b", 2); ("b", 3); ("b", 4); ("c", 5)]и я используюfun ((x1, y1),(x2, y2)) -> x1=x2 чтобы проверить на равенство, результат, который я хочу увидеть[("a", 1); ("b", 4); ("c", 5)], Смысл этой функции в том, что у меня есть входящие точки данных, где иногда точки данных имеют законную одинаковую метку времени, но я забочусь только о самой последней, поэтому я хочу выбросить предыдущие с той же меткой времени. Я реализовал следующую функцию:

let rec dedupeTakingLast equalityFn prev s = seq {
     match ( Seq.isEmpty s ) with
     | true -> match prev with 
                 | None -> yield! s
                 | Some value -> yield value
     | false ->
         match prev with 
         | None -> yield! dedupeTakingLast equalityFn (Some (Seq.head s)) (Seq.tail s) 
         | Some prevValue -> 
             if not (equalityFn(prevValue, (Seq.head s))) then 
                 yield prevValue
             yield! dedupeTakingLast equalityFn (Some (Seq.head s)) (Seq.tail s)
}

С точки зрения фактического выполнения работы, это работает:

> [("a", 1); ("b", 2); ("b", 3); ("b", 4); ("c", 5)] 
  |> dedupeTakingLast (fun ((x1, y1),(x2, y2)) -> x1=x2) None 
  |> List.ofSeq;;
val it : (string * int) list = [("a", 1); ("b", 4); ("c", 5)]

Однако с точки зрения производительности это катастрофа:

> #time
List.init 1000 (fun _ -> 1) 
|> dedupeTakingLast (fun (x,y) -> x = y) None 
|> List.ofSeq
#time;;    
--> Timing now on    
Real: 00:00:09.958, CPU: 00:00:10.046, GC gen0: 54, gen1: 1, gen2: 1
val it : int list = [1]    
--> Timing now off

Очевидно, что я делаю что-то очень глупое здесь, но я не вижу, что это такое. Откуда исходит хит производительности? Я понимаю, что есть лучшие реализации, но мне особенно интересно понять, почемуэтот реализация очень медленная.

РЕДАКТИРОВАТЬ: FYI, удалось выбрать достойную реализацию в функциональном стиле, который опирается наSeq. только функции Производительность в порядке, что в 1,6 раза больше времени, необходимого для реализации в императивном стиле.@gradbot ниже, который использует итераторы. Кажется, что корень проблемы заключается в использованииSeq.head а такжеSeq.tail в рекурсивных вызовах в моем первоначальном усилии.

let dedupeTakingLastSeq equalityFn s = 
    s 
    |> Seq.map Some
    |> fun x -> Seq.append x [None]
    |> Seq.pairwise
    |> Seq.map (fun (x,y) -> 
            match (x,y) with 
            | (Some a, Some b) -> (if (equalityFn a b) then None else Some a)  
            | (_,None) -> x
            | _ -> None )
    |> Seq.choose id