akimachoのはてなブログ

ICTとデザインのためのブログ

『プログラミングの基礎』読書日誌-18日目-

はじめに

今日は,第15章 新しい形の再帰をやっていきます.

一般的な再帰関数に必要なこと

  • 自明に答えが出るのはどのようなケースか
  • より小さな部分問題はどのようにしたら作れるか
  • 再帰呼び出しの結果から全体の結果がどのように得られるのか

分割統治

分割統治(divide and conquer)とは,以下の手順を踏む方法です.

  1. 問題を部分問題に分割する
  2. 各々の部分問題を独立に解く
  3. 得られた解から全体の解を計算する

分割統治法 - Wikipedia

クイックソート

クイックソートは,整列アルゴリズムの中でも計算量  O(nlogn)と早い方に分類されるソートです.以下の手順で,リストを整列します.

  1. 与えられたリストから,基準の要素(ピボット,pivot)を選択する.
  2. リストを基準の要素よりも大きい要素と小さい要素の2つのグループに分割する
  3. それぞれの要素を再び整列する
  4. 整列されたそれぞれのグループをまとめて,整列されたリストを得る

クイックソート - Wikipedia

OCamlによるクイックソートの実装

コードを見て,綺麗だなーと感動してしまいました.簡潔に書けるのですね.p.157より

(* 目的 : 受け取ったlstをクイックソートを使って昇順に整列する *)
(* quick_sort : int list -> int list *)
let rec quick_sort lst =
    (* 目的 : lstの中からnよりpである要素のみを取り出す *)
    (* take : int -> int -> (int -> int -> bool) -> int list *)
    let take n lst p = filter (fun item -> p item n) lst in
    (* 目的 : lstの中からnより小さい要素のみを取り出す *)
    (* take_less : int -> int list -> int list *)
    let take_less n lst = take n lst (<) in
    let take_greater n lst = take n lst (>) in
    match lst with
        [] -> []
        | first :: rest ->
                quick_sort (take_less first rest) @
                [first] @
                quick_sort (take_greater first rest)

停止性の確認方法

「一般に任意のプログラムを与えられてそのプログラムが停止するかどうかは決定不可能である」ことは,停止性問題として知られています.

停止性問題 - Wikipedia

ふじこのプログラミング奮闘記


本書では,プログラムの停止性を確認する方法が以下が紹介されていました.p.158

  1. 再帰呼び出しを行う際の部分問題が,何らかの意味でもとの問題よりも簡単になっていること
  2. それを繰り返すと,有限回で自明なケースに帰着されること

一般の再帰に対するデザインレシピ

テンプレート

自明に答えが出るケースとそれ以外のケースに場合分けをする.

本体

テンプレートに沿って,

  • 自明に答えが出るケースはどのような場合か
  • その場合の超えたは何か
  • 部分問題はどのようにしたら作れるか
  • 部分問題の結果から全体の結果を得るにはどうすればよいか

を考える

関数が完成したら,停止性の議論を行う.

おわりに

OCamlに関しては,『入門OCaml』と『プログラミング in OCaml』も読んでいます.あとで感想を書きたいと思います.

段々とOCamlの魅力,関数プログラミングの魅力がわかってきたような気がします(コードも書けるようにならないと・・・).

プログラミングの基礎 (Computer Science Library)

プログラミングの基礎 (Computer Science Library)

入門OCaml ~プログラミング基礎と実践理解~

入門OCaml ~プログラミング基礎と実践理解~