関数型プログラミングに入門した

概要

• こんにちは！先月末から プログラミングの基礎 を読んでいました。普段は Python や C 言語でプログラムを書くことが多いのですが、この本を通して、関数型プログラミングに入門しました。丁度今日に読み終えたので、なぜ読み始めたのかや何を学んだかなどの記録を残したいと思います。

読み始めたきっかけと目的

• この本を読もうと思ったきっかけは、関数型プログラミングを通して再帰の概念や多相型について学びたいと思ったからです。2, 3 年前までは競技プログラミングをしていたのですが、その時に再帰的なプログラムを書くのに苦手意識を感じていました。典型的な再帰の問題は解けるのですが、少し難しい応用的な問題が出ると、お手上げな状態でした。実務などで頻繁に使うイメージはないのですが、前々から苦手意識は潰しておきたいと思っていました。そのため、関数型プログラミング言語の OCaml を通して再帰的なデータ構造や多相型について学ぶことが、この本を読む目的でした。

学んだこと

• この本を通して学んだことを列挙します。
  • プログラムを書く際のデザインレシピとその実践
    • 関数の目的と入出力の型を考える
    • 関数のテストケース (具体例) を考える
    • 関数のテンプレート (骨組み) を実装する
    • 以上のことを基に関数の本体を実装する
    • テストケースに従って関数をテストする
  • 再帰的なプログラミング
  • リスト自体が再帰的なデータ構造である
    • 数学的帰納法をイメージするとわかりやすい
    • リストを定義するには、要素とリストが必要なので、再帰的なデータ構造となる
  • 関数の抽象化
  • 多相型を使用したデータ構造
  • エラーハンドリング

紹介

• ここでは、紹介されていたプログラムの中で、なるほど！と思ったプログラムについて紹介したいと思います。

• 接頭語のリストから全ての接頭語のリストを返す関数 prefix を実装することがこの章での目的です。例えば [1; 2; 3; 4] のリストを受け取ると、[[1]; [1; 2]; [1; 2; 3]; [1; 2; 3; 4]] を返す関数の実装です。

• 関数 prefix を実装する前に、まず関数 add_to_each を実装します。これは接頭語のリスト (int list list) を受け取るとリストの各要素の先頭に関数の引数から受け取った値 (int) を挿入する関数です。例えば [[1]; [1; 2]] のリストと挿入したい値 0 を受け取ると、[[0; 1]; [0; 1; 2]] を返す関数の実装です。

• まず、関数 add_to_each の目的と入出力の型について考えます。

(* 目的 : 受け取った lst の各要素の先頭に n を付け加える *)
(* add_to_each : int  -> int list list -> int list list *)

• 次に、関数のテストケースについて考えます。

(* テスト *) 
let test1 = add_to_each 1 [] = [];;
let test2 = add_to_each 1 [[2]] = [[1; 2]];;
let test3 = add_to_each 1 [[2]; [2; 3]] = [[1; 2]; [1; 2; 3]];;
let test4 = add_to_each 1 [[2]; [2; 3]; [2; 3; 4]]
                          = [[1; 2]; [1; 2; 3]; [1; 2; 3; 4]];;

• 次に、関数のテンプレートについて考えます。
• 複数のデータからなるデータの中身を取り出すには、パターンマッチを使います。これにより、リストの先頭の要素を表す first を介して要素にアクセスすることができる。

let rec add_to_each n lst = match lst with
    [] -> []
    | first :: rest -> [];;

• 最後に、これらを基に関数の本体を実装します。実装は以下になりました。
• rest に対して再帰的に関数 add_to_each を呼び出しています。これは、関数 add_to_each が受け取った lst の各要素 (今回はリスト) の先頭に n を付け加えます。初めに定義した目的が参考になります。その関数を rest に適用した結果は、 rest の各要素の先頭に n を付け加えたリストで、それとリストの最初の要素の先頭 first に n を付け加えた要素 ([n; first]) を結合すると、求めるべき結果を取得できます。また、サイズの小さいリスト rest を引数にしているので、再帰関数の停止性が担保されています。

let rec add_to_each n lst = match lst with
    [] -> []
    | first :: rest ->
        (n :: first) :: (add_to_each n rest) ;;

• 次に、実装するべき関数 prefix を関数 add_to_each を考えたフローと同様に考えます。

• まず、関数 prefix の目的と入出力の型について考えます。

(* 目的 : 受け取った lst から接頭辞のリストを求める *)
(* add_to_each : int list -> int list list *)

• 次に、関数のテストケースについて考えます。

(* テスト *) 
let test5 = prefix [] = [];;
let test6 = prefix [1] = [[1]];;
let test7 = prefix [1; 2] = [[1]; [1; 2]];;
let test8 = prefix [1; 2; 3; 4] 
                   = [[1]; [1; 2]; [1; 2; 3]; [1; 2; 3; 4]];;

• 次に、関数のテンプレートについて考えます。

let rec prefix lst = match lst with
    [] -> []
    | first :: rest -> [];;

• 最後に、これらを基に関数の本体を実装します。実装は以下になりました。
• ここでのポイントは (first :: []) :: add_to_each first (prefix rest) です。例えば lst が [1; 2; 3; 4] の場合を考えます。first には 1 が rest には [2; 3; 4] が入っています。そこで、まず [1] と [[1; 2]; [1; 2; 3]; [1; 2; 3; 4]] を作成し、それらを結合する方針で考えます。前者は first :: [] で作成できます。次に、後者について考えます。prefix rest は、[[2]; [2; 3]; [2; 3; 4]] を表しています。この結果を関数 add_to_each の第二引数に、第一引数に first を入れると、[[1; 2]; [1; 2; 3]; [1; 2; 3; 4]] が作成できます。こうして前者と後者の結果を結合すると目的の動作となります。その結果、以下の実装となりました。

let rec prefix lst = match lst with
    [] -> []
    | first :: rest ->
        (first :: []) :: add_to_each first (prefix rest);;

• 再帰関数にどんな入力を入れるとどんな結果が返るかを逆算することを意識しながら所望の関数を実装をすることが大事です。
• このように、ここで紹介したデザインレシピに従って様々な関数を OCaml を使用してプログラミングしていくのがこの本の特徴です。

まとめ

• ダイクストラのアルゴリズムや基本的なプログラムを関数型で実装することを通して、再帰の概念や多相型について学ぶことができました。また、再帰の関数を実装する際には、その関数の目的をしっかり考えて定義することの重要性を学びました。個人的には、関数型のプログラミングは数学チックで好みです。文法自体が再帰的なプログラムを書きやすくなっており、もっと多くのプログラムを書きたいです。実務で使うことはほとんど無いと思いますが、趣味で書くプログラムの幅が広がりそうです。理解があやふやな箇所もあるので、たくさん OCaml でプログラムを書いてから再度本を読み直したいと思いました。

• また、この本は関数型プログラミングの入門書としても最適だと思いました。

参考

• ProgrammingBasics
• プログラミングの基礎