プログラミング

【コード有】OCamlのリスト基本操作まとめ(取り出し・追加・結合・削除・最大値・逆順)

大学の課題や関数型言語の操作に慣れていない人にとってはリストの操作一つとってもなかなか慣れるまでは難しいです。

しかし、逆に言えば、慣れてしまえばスラスラとコードが書けるようになります。今回はOCamlのリスト操作の基本的な考え方を解説していきたいと思います^^

なお、今回ではOCamlの基礎的なことのみを分かっている体で進めていきます。

OCamlのリスト基本操作の考え方

「先頭と残り」という考え方

OCamlではリストをhead::restという風に「先頭と残り」で分割します。
例えば、リスト[1;2;3;4;5]の中から3を取り出したい時を考えてみましょう。


まず、リストの先頭にある1と3を比較します。1と3は等しくないため、1を捨てて2と3を比較します。2と3も等しくないため、2を捨てて3と3を比較します。これは等しいため、結果として「3」を出力します。

これを別の形で表したいと思います。まずは

[1;2;3;4;5]の先頭(=1)と3を比較します。

次に、1を取り除いた

[2;3;4;5]の先頭(=2)と3を比較します。

次に、[3;4;5]の先頭(=3)と3を比較します。

これで結果「3」を出力する形になります。

まとめ

  • [1;2;3;4;5]と3で比較
  • [2;3;4;5]と3で比較
  • [3;4;5]と3で比較

再帰の考え方

では、[1;2;3;4;5]から[2;3;4;5]や[3;4;5]へ移るはどうやれば良いでしょうか。

OCamlのプログラム上で[1;2;3;4;5]のリストをhead::restと分割します(headやrestでなくても、a、bみたいな書き方でもOK)。

OCamlではリストを「先頭と残り」という風に分割するため、ここでのheadは1、restは[2;3;4;5]になります。

そしてこのrest([2;3;4;5])をさらにhead::restで分けると、headが2、restが[3;4;5]になりますね^^

そして、残ったリストに対して毎回同じ操作を行う(先頭と3を比較する)ので、これはまさに再帰的なプログラムです。

再帰の考え

  1. リストの先頭と3を比較
  2. 先頭を取り除いたリストの先頭と3を比較
  3. そのリストの先頭を取り除いたリストの先頭と3を比較

のようにかけますが、「リストの先頭と3を比較」という全く同じ文言が出現しているのが分かるかと思います。したがって、例えばリストの先頭と3を比較する関数を"search list num"(listとnumは引数)という名前にすれば、

  • リスト(head::rest)に関数search(list 3)を適用
  • rest(head1::rest1)にsearchを適用
  • rest1にsearchを適用

という風に表現できますね!これをOCamlのプログラムで表現していきましょう!

OCamlリスト基本操作まとめ

取り出し

let rec search list num = match list with
    [] -> raise Not_found 
    |[a] -> if a = num then num else raise Not_found
    |head::rest -> if head = num then num else search rest num
;;

引数はリストと任意の型(numと書いているから数字っぽく思うかもしれませんが、stringやcharでもOKです!)になります。

まずはリストの場合分けですが、空リストの場合はそもそも取り出す要素がないので「Not_found」を出力します。

次にすぐhead::restにしても良いのですが、僕は癖で上のように書いてしまいます。

head::restでlistを先頭と残りに分けたら、先頭とnumを比較して、等しければnum、あるいはheadを出力して終了、等しくなければ、リストの残り部分(rest)と3でsearchを適用します。これを繰り返すことで等しいものが見つかるまでどんどんリストが短くなっていきます。

let list1 = [1;2;3;4;5];;
let list2 = [1;4;9;16;25];;

search list1 3;;
search list2 3;;
取り出し
実行結果

追加

let add list num = match list with 
    [] -> [num]
    |_ -> num::list 
;;

これに関してはただ追加していくだけなので再帰は必要ありません。

let list1 = [1;2;3;4;5];;
add list1 0;;
追加
2行目が「raise Not_found」になっていますが間違いです。正しくは[num]です。


応用 : リストの後ろに追加する

let rec add2 list num = match list with 
    [] -> [num]
    |[a] -> [a;num] 
    |head::rest -> head :: (add2 rest num);;


前に追加する場合と異なり再帰が必要になります。少し分かりにくいかもしれないので操作を具体的に見ていくと(都合上リストの[]を()と表現しています)以下の通りです。


  • (1;2;3;4;5)を見る

    これは空リストでもなければ、要素が一つでもないので、4行目の「head::rest」のところに移動する。headは1でrestは(2;3;4;5)


  • headを先頭に、その後ろで残りのリスト(2;3;4;5)に対してadd2を適用

    [2;3;4;5]も空リストでも要素が一つでもないので4行目の「head::rest」に移動。headは2、restは(3;4;5)。ここでの形は、

    1(最初のhead) :: 2(今回のhead) :: add2 rest(3;4;5)となっている。


  • (3;4;5)でadd2を適用

    1 :: 2 :: 3 :: add2 rest(4;5)となる


  • (4;5)でadd2適用

    1 :: 2 :: 3 :: 4 :: add2 rest(5)となる。


  • (5)でadd2適用

    これは要素が一つのリストだから、3行目の「(a) -> (a;num)」を適用する。これより、

    1 :: 2 :: 3 :: 4 :: [5;6]となり、最終的に(1;2;3;4;5;6)となる。



結合

let rec append list1 list2 = match list1 with 
    [] -> list2
    |[a] -> a :: list2
    |head::rest -> head :: (append rest list2);; 

今やったリストの後ろに追加するのと似ています。3行目の部分が意外と重要です。

let listA = [1;2;3;4;5];;
let listB = [6;7;8;9;10];;

append listA listB;;
結合


削除

let rec delete list num = match list with
    [] -> []
    |[a] -> if a = num then [] else [a]
    |head::rest -> if head = num then rest else head :: (delete rest num) ;;

4行目のrestの後ろのheadを忘れないようにしましょう!もし忘れると、削除する手前の要素も全部道連れになってしまいます。

let list = [1;2;3;4;5];;
delete list 3;;
削除


最大値

let rec max list = match list with 
    [] -> raise Not_found
    |[a] -> a
    |[a;b] -> if a > b then a else b
    |first::second::rest -> if first > second then max (first::rest) 
                                         else max (second::rest);;

リストの先頭と次の要素を比べ、大きかった方を残りのリストの先頭と比べる作業を繰り返します。

let list = [4;5;3;12;-4;3;5];;
max list;;
最大値


リストを逆順に表示

let rec append list1 list2 = match list1 with 
    [] -> list2
  |[a] -> a :: list2
  |head::rest -> head :: (append rest list2);; 

let rec reverse list = match list with 
    [] -> []
  |[a;b] -> [b;a]
  |head::rest -> append (reverse rest) [head];;

先ほどの結合のプログラムを使用します。


OCamlリスト基本操作まとめ : 慣れれば簡単

OCamlをはじめとする関数型言語の情報は少なく、あったとしてもあまり整理されていないものが多かったので今回このような形でまとめさせていただきました。

最初はリスト操作に慣れず難しいと感じていても、一旦コツを掴むとすぐに出来るようになるので是非今回の記事を参考に練習してみてください!

  • この記事を書いた人
おととらべる

おととらべる

現役理系大学生。 Programming : Java, Python 音楽活動名義はRoot Introvertです。 音楽制作でのリリース、プロモーション ByeByeCopyright -> Root Introvert - Between Our Hearts (2019年3月) AirwaveDubstepTV -> SHADOWKEY - Kiss Me(feat. Jellow) (Root Introvert Remix) (2019年10月) NoCopyrightNation(NCN) -> Root Introvert - You Don't Wanna Be Lonely(2020年2月) 7even EDM -> Root Introvert - You Don't Wanna Be Lonely(Promotion) (2020年3月、4月) InspiredByInspired -> Root Introvert - You (2020年2月) AshesToFlame Records -> Root Introvert & Isura - Reminiscent (2020年4月) 一人旅 : タイ、ラオス、ベトナム、マレーシア

-プログラミング
-, , , , , , , , , ,

© 2020 おととらべる Powered by AFFINGER5