質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.36%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

OCaml

OCaml(オーキャムル)は、フランスのINRIAが開発した関数型言語MLの一種で、 最新の言語理論の成果が取り入れられているプログラミング言語です。

Q&A

解決済

1回答

1975閲覧

ocamlによる目次の作成

grape_ll

総合スコア83

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ループ

ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

関数

関数(ファンクション・メソッド・サブルーチンとも呼ばれる)は、はプログラムのコードの一部であり、ある特定のタスクを処理するように設計されたものです。

OCaml

OCaml(オーキャムル)は、フランスのINRIAが開発した関数型言語MLの一種で、 最新の言語理論の成果が取り入れられているプログラミング言語です。

0グッド

0クリップ

投稿2021/05/16 03:00

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

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

ocaml

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

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

ocaml

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

(3)

ocaml

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

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

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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

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

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

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


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

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

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

ocaml

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

やり方

  • 長さnを与えると、[1; 2; .. n]の数列を作成する関数sequenceを定義する(再帰を用いる)
  • List.lengthBIG_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重のリストになっていることに注意)

ocaml

1(* nested_list *) 2[ [("apple", 1); ("grape", 1)]; 3 [("orange", 2); ("apple", 2)]; 4 [("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.concatnested_listをフラットな最終形のリストに変換する。

ocaml

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

補足

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

投稿2021/05/16 05:33

編集2021/05/16 06:19
tatsuya6502

総合スコア2046

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

grape_ll

2021/05/16 07:43

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.36%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問