3

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

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

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

4

2 回答 2

2

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

(* [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某种方式累积，所以折叠，但是你想要快捷方式失败早期语义......）我不'看不到任何优势。

于 2012-02-17T05:45:40.833 回答
1

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

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)
于 2012-02-17T07:23:15.937 回答