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 回答