3

私はOCamlで作業しており、リスト内のすべての要素を互いにチェックする必要があるリストがあります。リストは、基本単位または派生単位のいずれかの単位のリストです。基本単位は m、s、g であり、派生単位は、kg、min、ft、lb など、m、s、g を使用する任意の単位です。

したがって、リストの例は [lb; フィート; m]。ft と m は同じ基本単位 m を共有しているため、このリストは無効です。より明確にするために[lb; kg; s] は無効になります。これは、lb と kg が同じ基本単位 m を共有しているためです。ただし [ft; s; 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何らかの方法で蓄積する必要があるため、折り畳みが必要ですが、ショートカットの Fail-Early セマンティクスが必要です...)。何の利点もありません。

于 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 に答える