OCaml:计算对列表中的不同值

Question

我有一个配对列表

let myList=[(0,1);(0,2);(0,3);(1,5);(2,4);(3,5);(5,4);(5,6);(4,3)];;

为了计算列表中存在的每个单独的不同值，我有这个过程

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

代码运行正确，但我的问题是:

有没有更优雅或更有效的方法来做到这一点？ 例如一个独特的功能而不是两个

Answer 1

您的方法有效，简单易懂。它唯一的缺点是您的代码使用了 Shlemiel the painter's algorithm .这意味着，处理时间表现为列表大小的二次函数。

如果要去掉，用sets比较合适:将列表中的所有数字添加到一个集合中并计算其大小。现在时间性能在 n log(n) 中并且扩展性更好。

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

这段代码使用了一个累加器acc，它通过迭代来填充 在名单之上。读取完所有列表后，返回累加器中的元素数。