Count occurrences of an element in a list

5
votes

I have a list of integers and any integers that occur multiple times will do so consecutively. I would like to convert this to a list of tuples, containing each object together with its count.

I have come up with the below, but there is a problem with the return type of temp: "The type 'int' does not match the type ''a list'". However, the three return types look consistent to me. What have I done wrong? If what I've done is not good F# and should be done in a completely different way, please also let me know.

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
    | [] -> []
5
f#

5 Answers

28
votes

EDIT: Oops, this does not answer your question, since you said "consecutive". But I'll leave it here since someone searching the question title may find it useful.

Seq.countBy does this.

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)]
9
votes

What about this one?

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

In this line:

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

the compiler interprets your code as

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

but what you want is

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

However, even with this change, one problem with your algorithm is that the temp function is not tail-recursive, which means that it can cause a stack overflow when called on a long list (e.g. countoccurences [1..10000] fails on my machine). If this is important to you, then you should rewrite your temp helper function to be tail recursive. The easiest way to do this is to add an accumulated list parameter and reverse the list afterwards.

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
    | [] -> []
1
votes

I would probably use a mutable solution for this. Maybe something like:

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|)

EDIT

I forgot about countBy (which is implemented similarly).

1
votes

If you're using recursion to traverse a list, you can always use fold.

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