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
我该如何修复它? ㅤㅤㅤㅤㅤㅤㅤㅤ
根据您的错误,似乎
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'