Подсчет вхождений элемента в списке

Question

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

Я придумал ниже, но есть проблема с типом возвращаемого значения temp: "тип 'int' не соответствует типу '' список '". Тем не менее, три типа возвращаемых данных выглядят в соответствии со мной. Что я сделал не так? Если то, что я сделал, не является хорошим F # и должно быть сделано совершенно другим способом, пожалуйста, дайте мне знать.

let countoccurences list =
    match list with
    | x::xs -> let rec temp list collecting counted =
                    match list with
                    | x::xs when x=collecting -> temp xs collecting counted+1
                    | x::xs -> (collecting,counted)::temp xs x 1
                    | [] -> (collecting,counted)::[]
               temp xs x 1
    | [] -> []

Answer 1

РЕДАКТИРОВАТЬ: Ой, это не отвечает на ваш вопрос, так как вы сказали "последовательно". Но я оставлю это здесь, так как кто-то, ищущий название вопроса, может найти это полезным.

Seq.countBy делает это.

let list = [1;2;3;4;5;6;1;2;3;1;1;2]
let results = list |> Seq.countBy id |> Seq.toList 
printfn "%A" results
// [(1, 4); (2, 3); (3, 2); (4, 1); (5, 1); (6, 1)]

Answer 2

А как насчет этого?

lst |> Seq.groupBy (fun x -> x) |> Seq.map (fun (a,b) -> (a, Seq.length(b)))

Answer 3

В этой строке:

| x::xs when x=collecting -> temp xs collecting counted+1

компилятор интерпретирует ваш код как

| x::xs when x=collecting -> (temp xs collecting counted)+1

но вы хотите

| x::xs when x=collecting -> temp xs collecting (counted+1)

Однако, даже с этим изменением, одна проблема с вашим алгоритмом заключается в том, что функция temp не является хвостовой рекурсией, что означает, что она может вызвать переполнение стека при вызове из длинного списка (например, при сбое countoccurences [1..10000] моя машина). Если это важно для вас, то вам следует переписать вашу вспомогательную функцию temp, чтобы она была хвостовой рекурсивной. Самый простой способ сделать это - добавить накопленный параметр списка и затем перевернуть список.

let countoccurences list =
    match list with
    | x::xs -> 
        let rec temp list collecting counted acc =
            match list with
            | x::xs when x = collecting -> temp xs collecting (counted+1) acc
            | x::xs -> temp xs x 1 ((collecting, counted)::acc)
            | [] -> (collecting, counted)::acc
        temp xs x 1 []
        |> List.rev
    | [] -> []

Answer 4

Если вы используете рекурсию для обхода списка, вы всегда можете использовать сложение.

let countOccurrences = function
| []    -> []
| x::xs -> ([(x,1)],xs)
           ||> List.fold(fun ((y,c)::acc) x -> if x = y then (y,c+1)::acc else (x,1)::(y,c)::acc) 
           |> List.rev

Answer 5

Я бы, вероятно, использовал изменяемое решение для этого.Может быть что-то вроде:

let countOccurrences l =
    let counts = System.Collections.Generic.Dictionary()
    l |> List.iter (fun x -> 
        match counts.TryGetValue(x) with
        | true, i -> counts.[x] <- i + 1
        | _ -> counts.Add(x, 1))
    counts |> Seq.map (|KeyValue|)

РЕДАКТИРОВАТЬ

Я забыл о countBy (который реализован аналогично).