如何编写一个函数来使用Map计算列表中元素的数量？

Question

module IntMap = Map.Make(struct type t = int let compare = compare end)

let rec count_with_map (il: int list) =
  match il with
  | [] -> []
  | head :: tail ->
    match count_with_map tail with
    | (c, n) :: tail when head = n -> (head, n + 1) :: tail
    | tail -> (head, 1) :: tail ;;

我认为这是正确的，但我一直收到此错误。

Error: This expression has type (int * int) list
       but an expression was expected of type 'a Count_with_map.IntMap.t

Answer 1

根据您的错误，似乎

count_with_map

应该返回

int IntMap.t

值而不是列表。不过，您的函数返回一个列表。您似乎正在尝试返回关联列表。 这种方法可以工作，但由于关联列表中查找和更新的 O(n) 性质，效率较低。另一方面，由于映射被实现为平衡二叉树，因此具有 O(log n) 查找和更新。

让我们看看递归的基本情况：空列表。这巧妙地映射到一个空的map，这非常容易表达。

let rec count_with_map = function
  | [] -> IntMap.empty

现在，如果列表不为空，我们可以回显您在列表尾部运行操作的方法。这将返回一张地图。

let rec count_with_map = function
  | [] -> IntMap.empty
  | h::t ->
    let map = count_with_map t in
    ...

现在，我们无法对

int IntMap.t

值进行模式匹配，因为该类型是抽象的，但我们可以使用

IntMap.update

来更新或插入该映射。地图是不可变的数据结构，因此我们正在创建一个新地图。

let rec count_with_map = function
  | [] -> IntMap.empty
  | h::t ->
    let init_or_update = function
      | None -> Some 1
      | Some n -> Some (n + 1)
    in
    let map = count_with_map t in
    let map' = IntMap.update h init_or_update map in
    map'