如何在 OCaml 中创建一个字典，将第一个列表的每个元素与其在第二个列表中出现的次数相关联？

Question

我有两个列表，[“0”，“1”]和[“0”，“1”，“0”]，我想得到一个列表，[（0,2），（1,1） ], - 将第一个列表的每个元素与其在第二个列表中出现的次数相关联。我试过这个：

let partialSolution = 
List.map(
    fun x -> 
        let subsubList = List.for_all  (fun y -> (String.compare x y)=0) ) ("0"::("1"::("0"::[]))) in
 (x, List.length ( List.filter ( fun z -> z = true) subsubList ) ) 
) ;;

，但这不好：它给了我这些错误：

# let partialSolution = 
# List.map(
#     fun x -> 
#         let subsubList = List.for_all  (fun y -> (String.compare x y)=0) )
File "", line 4, characters 73-74:
Error: Syntax error: operator expected.
#  ("0"::("1"::("0"::[]))) in
File "", line 4, characters 99-101:
Error: Syntax error
#  (x, List.length ( List.filter ( fun z -> z = true) subsubList ) ) 
# )
File "", line 6, characters 0-1:
Error: Syntax error
#  ;;
File "", line 6, characters 2-4:
Error: Syntax error

我想了解如何解决这个问题 - 我是 OCaml 的新手。

Answer 1

你对括号有点过于热心了。语法错误是由

(fun y -> ...)

后面额外的右括号引起的。

但是您仍然会遇到类型错误，因为

List.for_all

返回

bool

，如果所有项都满足谓词，则返回

true

，否则返回

false

。看来你想在这里使用

List.map

来代替。

您也不需要在每次使用

::

时都用括号括起来。

("0"::"1"::"0"::[])

很好，但您也可以将其简化为简单的列表文字：

["0"; "1"; "0"]

。此外，

z = true

相当于

z

，尽管可读性可能稍差一些。

这可以编译。我还没有检查它是否真的达到了你想要的效果：

let partialSolution = 
    List.map
        begin fun x -> 
            let subsubList =
                List.map
                    (fun y -> String.compare x y = 0)
                    ["0"; "1"; "0"]
            in
            (x, List.length (List.filter (fun z -> z) subsubList)) 
        end

此外，如果您使用 4.03 或更高版本，您可以使用

String.equal

，如果您使用 4.08，您可以使用

Fun.id

代替临时 lambda 函数：

let partialSolution = 
    List.map
        begin fun x -> 
            let subsubList =
                List.map (String.equal x) ["0"; "1"; "0"]
            in
            (x, List.length (List.filter Fun.id subsubList)) 
        end

或者您可以使用

bool list

直接进行计数，而不是处理中间

List.fold_left

：

let partialSolution = 
    List.map
        begin fun x -> 
            let count =
                List.fold_left
                    (fun count y ->
                        if String.compare x y = 0 then
                            count + 1
                        else
                            count)
                    0 ["0"; "1"; "0"]
            in
            (x, count) 
        end

Answer 2

作为替代方案提出：使用地图来有效地计算结果。首先，我们创建一个映射，其中第一个列表的元素是绑定到

0

的键。

然后我们折叠第二个列表，更新映射中的值if它已经是映射中的键的元素。如果第二个列表中的元素不在第一个列表中，则模式匹配中的

None -> None

情况不会执行任何操作。

然后我们可以使用

StrMap.bindings

来获取对应的关联列表。

运行时复杂度为 O(len(lst2) * log(len(lst1)))。

module StrMap = Map.Make (String)

let count lst1 lst2 =
  let map = 
    List.fold_left 
      (fun m x -> StrMap.add x 0 m) 
      StrMap.empty 
      lst1 
  in
  lst2
  |> List.fold_left 
       (fun m x -> 
          StrMap.update 
            x 
            (function 
             | None -> None 
             | Some c -> Some (c + 1)) 
            m) 
       map
  |> StrMap.bindings

测试这个：

# count ["0"; "1"] ["0"; "1"; "0"; "2"];;
- : (string * int) list = [("0", 2); ("1", 1)]