Как я могу удалить дубликаты в последовательности F # без использования ссылок

Question

У меня есть отсортированная последовательность, и я хочу просмотреть ее и вернуть уникальные записи в последовательности. Я могу сделать это, используя следующую функцию, но она использует ссылочные переменные, и я не думаю, что это правильный способ решения проблемы.

    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
        }

Как мне это сделать функционально?

Answer 1

[1;1;1;2;2;2;3;3;3]
|> Seq.distinctBy id
|> printfn "%A"

Answer 2

Seq.distinct (1::[1..5]) возвращает seq [1; 2; 3; 4; 5].Это то, что вы имели в виду?

Answer 3

distinct и distinctBy оба используют Dictionary и поэтому требуют хеширования и немного памяти для хранения уникальных предметов.Если ваша последовательность уже отсортирована, вы можете использовать следующий подход (аналогичный вашему).Он почти вдвое быстрее и постоянно использует память, что делает его пригодным для последовательностей любого размера.

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

Я не мог найти способ использовать mutable s вместо ref s (если не считать ручного кодирования перечислителя), , который, я уверен, значительно ускорит его (я пробовал - без разницы).

Answer 4

Просто инициализируйте уникальную коллекцию (например, набор) с помощью следующей последовательности:

set [1; 2; 3; 3; 4; 5; 5];;
=> val it : Set<int> = set [1; 2; 3; 4; 5]

Answer 5

В моем случае я не мог использовать Seq.distinct, потому что мне нужно было сохранить порядок элементов списка.Я использовал решение от http://ocaml.org/learn/tutorials/99problems.html. Я думаю, что оно довольно короткое

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

Answer 6

Решение, приведенное ниже, сохраняет порядок элементов и возвращает только первое вхождение элемента в общем списке. Конечно, это создает новый список с удаленными лишними элементами.

//  ****  Returns a list having 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
    lst 
    |> 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]