akimachoのはてなブログ

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

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

はじめに

今日は,第9章リストについて勉強していきます.ちょっと長いので2回に分けます.

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

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

リストとは

リストとは,同じ型のデータを任意の個数並べたデータのことです.組では扱えるデータの個数は有限個でした.しかし,組では任意の型を扱うことができるのに対し,リストは同じ型を要素にしなければなりません.表にしてみると次のようになります.

データ構造 個数
リスト 任意の個数 同じ型
限られた個数 任意の型

最も簡単なリストは空リストと呼ばれる要素が0個のリストで,OCamlでは空リストを[]と表記します.

リストの操作

リストの先頭に要素を付け加える命令をcons(コンス)と呼び,::と表記します.::は右結合になります.また,::の左側には要素,右側にはリストがきます.以上から,以下のコードの2式は,

2 :: 1 :: []
2 :: (1 :: [])

は同じになり,リスト1 :: []に2をコンスすると解釈することができます.このようにコンスにより構成していくリストをConsリストとも呼びます(大川徳之『関数プログラミング実践入門』p.115).またリストを空集合を書かず方法もあります.次のようになります.

[2; 1]

なお,以上の式はint list = [2; 1],つまりint list型として評価されます.

リストの厳密な定義

リストの厳密な定義は次のようになります.

1. 空リスト[]はリストである.
2. firstが要素,restがリストならfirst::restもリストである.
p.71

確かにこの定義ならば漏れがないですね.

  • 0個の場合,[]
  • 1個の場合,a::[]
  • 2個の場合,b::a::[]

のようにドミノ倒しのように定義するようになってます.ところで,この定義はリストを定義づけるためのものですが,その中でリスト自体を使っています.このような定義を再帰的定義(機能的定義)と呼びます.(『計算機科学入門』p.36)本書ではデータ型の定義なので,再帰的なデータ型,自己参照をするデータ型と呼ばれてます.

私は次の文を読んで再帰的定義のこころがわかったように感じました.

再帰的なデータ型には,必ず自己参照をしていない無条件に使うことができるケースが存在します.そして,それを種にして自己参照しているケースを何度も使うことで,任意に大きなデータを作り上げていきます。(p.72)

リスト (抽象データ型) - Wikipedia

計算機科学入門 (Information & computing (1))

計算機科学入門 (Information & computing (1))

リストとパターンマッチ

組やレコードと同じように,リストでもパターンマッチを使います.しかし,リストの要素を取り出す場合,空リストや長いリストの場合を考えなければいけません.そのため,パターンマッチの構文は以下のように書くことができます.ただし,式1〜式nはすべて同じ型である必要があります.

matchwith 
      パターン1 ->1
    | パターン2 ->2
    | パターン3 ->3
    | パターンn -> 式n

パターンマッチの構文は,

  1. matchとwithではさまれた式を実行する
  2. 1の結果がどのパターンにマッチするか上から順に探索する
  3. 最初にマッチしたものが見つかったら,該当の式を実行する

の順に実行されていきます.

リストから要素を取り出すパターンマッチ

matchwith
      [] ->1 (* リストが空だった場合の式 *)
    | first :: rest ->2 (* リストが空でない場合の式 *)

練習問題

問題9.3までやりました.


第9章問題その1

おわりに

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

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