I have a list of pairs
let myList=[(0,1);(0,2);(0,3);(1,5);(2,4);(3,5);(5,4);(5,6);(4,3)];;
For count each single distinct value present in list I have this procedure
let rec flat lst visited =
match lst with
[]->visited
| (x,y)::xs -> flat xs (x::y::visited)) ;;
let newLst = flat myList [];;
val newLst : int list =
[4; 3; 5; 6; 5; 4; 3; 5; 2; 4; 1; 5; 0; 3; 0; 2; 0; 1]
let rec count lista =
match lista with
[]->0
| x::xs ->
if (List.mem x xs) then count xs
else 1+count xs;;
count newLst;;
- : int = 7
The code run correctly but my question is:
Is there a more elegant or efficent way to do this? For example a unique function and not two?
Your method works, is simple, and easy to understand. Its only downside, is that your code uses the Shlemiel the painter's algorithm. Here this means, that processing time behaves as a quadratic function of the size of the list.
If you want to remove it, it is appropriate to use sets: add all the numbers in your list to a set and compute its size. Now the time performance is in n log(n) and scales much better.
let myList=[(0,1);(0,2);(0,3);(1,5);(2,4);(3,5);(5,4);(5,6);(4,3)]
module IntegerSet = Set.Make(struct
type t = int
let compare = Pervasives.compare
end)
let count lst0 =
let rec loop acc lst =
match lst with
| [] -> IntegerSet.cardinal acc
| (a,b)::tl -> loop IntegerSet.(add b (add a acc)) tl
in
loop IntegerSet.empty lst0
This code uses an accumulator acc which is filled in by iterating over the list. When all the list has been read, the number of elements in the accumulator is returned.