ocamlによる目次の作成

Question

###実装したい内容
[ ["apple";"grape"] ; ["orange";"apple"] ; ["lemon";"melon";"banana"] ] (=BIG_list)
のような文字列のリストのリストが引数として与えられたときに
[ ("apple",1) ; ("apple",2) ; ("grape", 1) ; ("orange",2); ... ; ("banana",3) ]
のようなリストを返す関数

###現段階で私が考えている実装方法
(1)指定した要素がリスト内に属しているかを返すmember関数を作る

#let rec member string list =
  match list with
  | [] -> false
  | h::t -> (string=h) || member string t;;

（2）重複なしの文字列によるリストを生成する
["apple";"grape";"orange";"lemon";"melon";"banana"]　(=ELE_list)
そのためにBIG_listの要素をある入れてこれを作れるような関数を考える
次の応用

# let rec unduplicate a =
match a with
| [] -> []
| h::t -> if member h t then unduplicate t
else h::unduplicate t;;

(3)

math BIG_list with
| [] -> []
| h::t -> member string h

のような形でELE_listの要素がBIG_list中のリストに含まれているかを確認していく(再帰を用いる)．このときcountなどの変数で，今のhがBIG_list中の何番目かを数え，member関数がtrueならば，そのcountと文字列のタプルを格納する．

###問題点
(2)まではなんとか実装の方法を具体的に組めそうなのですが，(3)はやる内容が複雑で，二重のループを組む必要があるので，そこの具体的な実装が思い浮かびません．

###教えていただきたいこと
現段階の私の方法に具体的な実装，もしくは，新たな実装のアルゴリズム

Answer 1

(3)はやる内容が複雑で，二重のループを組む必要があるので，

(3)を1つの再帰関数でやろうとせずに、いくつかの再帰関数に分けて、それぞれをシンプルなループ（二重になってないループ）にすれば実装できるかもしれません。

たとえば以下のように2つの再帰関数に分けられます。

• (3a)の関数：（外側のループ） ELE_listの要素（アイテム名）を1つずつ取り出して、BIG_listと共に(3b)の関数を適用する
• (3b)の関数：（内側のループ）　アイテム名とBIG_listを引数にとり、そのアイテムが出てくるBIG_listの要素番号を調べる。結果を[(アイテム名, 要素番号); ..]の形で返す。例：アイテムが"apple"なら[("apple, 1); ("apple", 2)]を返す

学習のためにあえて再帰関数で実装する道を選んでいるのかもしれませんが、特に縛りがないのなら再帰関数よりもList.mapなどを活用するのがお勧めです。その方が直感的に書けることが多いです。

---

もしくは，新たな実装のアルゴリズム

自分ならこうするかなあ、というアルゴリズムを紹介します。方針として、できるだけ再帰関数を書かず、List.combineやList.concatなどOCamlのライブラリー関数を活用しています。なお、私自身はOCamlは使っておらず、仕事で使っている他の言語（ErlangとRust）での経験を元にしています。ですからこれがOCamlらしい書き方なのかは分かりません。

(1) BIG_listを以下の「要素と要素番号の組」のリストnumbered_listへ変換する。

(* numbered_list *)
[ (["apple"; "grape"], 1);
  (["orange"; "apple"], 2);
  (["lemon"; "melon"; "banana"], 3) ]

やり方

• 長さnを与えると、[1; 2; .. n]の数列を作成する関数sequenceを定義する（再帰を用いる）
• List.lengthでBIG_listの長さを求め（例：3）、sequence関数で同じ長さの数例を作る（例：[1; 2; 3]）
• List.combineを使って、BIG_listと数列を上記のnumbered_listへと変換する

(2) numbered_listの各要素（例：(["apple"; "grape"], 1)）を[("apple, 1"); ("grape, 1)]の形に変換することで、以下のようなnested_listを作成する。（2重のリストになっていることに注意）

(* nested_list *)
[ [("apple", 1); ("grape", 1)];
  [("orange", 2); ("apple", 2)];
  [("lemon", 3); ("melon", 3); ("banana", 3)] ]

やり方

• (["apple"; "grape"], 1)から[("apple, 1"); ("grape, 1)]へ変換する関数を定義する（第1引数["apple"; "grape"]に対してList.mapを使う）
• List.mapを使い、その関数をnumbered_listへ適用することでnested_listへと変換する

(3) List.concatでnested_listをフラットな最終形のリストに変換する。

[ ("apple", 1);
  ("grape", 1);
  ("orange", 2);
  ("apple", 2);
  ("lemon", 3);
  ("melon", 3);
  ("banana", 3) ]

補足

• なお、(2)のList.mapと(3)のList.concatを一度に行うList.concat_mapもある

Comments

[grape_ll]

教えていただいたアルゴリズムでは，無事作ることが出来ました．
ありがとうございます．
自分のアルゴリズムでも，ご助言してくださったことを参考に組んでみたいと思います．