algorithm - 相互检查列表中的每个值

Question

我正在使用 OCaml，我有一个列表，我需要在其中相互检查列表中的所有元素。该列表是单位列表，可以是基本单位也可以是派生单位。基本单位是 m、s、g，派生单位是任何使用 m、s、g 的单位，例如 kg、min、ft、lb 等。

因此，示例列表是 [lb;英尺；米]。此列表无效，因为 ft 和 m 共享相同的基本单位:m。更清楚 [lb;公斤; s] 将无效，因为 lb 和 kg 共享相同的基本单位:m。然而[英尺; ; m] 是完全有效的。这些基本单位转换保存在哈希中以供查找。

我的问题是如何相互检查所有单元。我试过使用折叠，但它让我的头很痛。谁能帮帮我？

Answer 1

具有二次复杂度的简单解决方案:

(* [check_pair] should return [false] if check fails *)
let rec check_each_pair check_pair = function
  | [] -> true
  | hd1 :: rest ->
    let rec check_rest = function
      | [] -> true
      | hd2 :: rest -> check_pair hd1 hd2 && check_rest rest
    in
    check_rest rest && check_each_pair check_pair rest

请注意，内部 check_rest 仅检查列表中每个元素的谓词。那就是 List.for_all。

let rec check_each_pair check_pair = function
  | [] -> true
  | hd1 :: rest ->
    List.for_all (check_pair hd1) rest && check_each_pair check_pair rest

你可以疯狂组合器，也可以将 check_each_pair 实现为对递归组合器的调用，但这不是直接的(你需要以某种方式累积 rest，所以折叠，但是你想要快捷方式 fail-early 语义...)而且我看不出有任何优势。