Number of entries in the list

Question

I have a list of integers, and any integers that happen multiple times will do this sequentially. I would like to convert this to a list of tuples containing each object along with its counter.

I came up with below, but there is a problem with the temp return type: “The int type does not match the list type. However, the three return types look consistent with me. What have I done wrong? If what I did is not is a 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 | [] -> [] 

Answer 1

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 you want

 | 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 in a long list (for example, countoccurences [1..10000] my machine). If this is important to you, you should rewrite your temp helper function so that it is recursive. The easiest way to do this is to add the accumulated list parameter and subsequently cancel the list.

 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 2

EDIT: Oh, that doesn't answer your question since you said "sequentially." But I will leave it here, as someone looking for the title of a question might find this 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)] 

Answer 3

How about this?

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

Answer 4

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

Answer 5

If you use recursion to move through the 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