相互检查列表中的每个值

Question

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

因此示例列表为 [lb;英尺；米]。该列表无效，因为 ft 和 m 共享相同的基本单位：m。更清楚地说[lb;公斤； s] 将无效，因为 lb 和 kg 共享相同的基本单位：m。然而[ft; s; 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 ，所以折叠，但然后你想要快捷方式早期失败语义...）并且我没有看到任何优势。

Answer 2

一个简单的解决方案是首先从列表中创建所有对的列表（通过使用 笛卡尔积列表及其自身）并稍后检查对列表上的条件：

let cartesian xs ys =
    List.concat (List.map (fun x -> List.map (fun y -> (x, y)) ys) xs)

let haveDifferentBases(x, x') =
   (* check whether they have different base units *)

let check_all_pairs xs =
   List.for_all haveDifferentBases (cartesian xs xs)