Home
☰

代数プログラミング入門 Ch5 代数的データ型1

資料
Published on 2024-10-18 under the tag algebra, lecture, statistics, haskell

Table of Contents

1 代数的データ型(集合論的解釈)

Haskellのデータ型はすべて代数的データ型です. 代数的データ型には, 列挙型,直積型,直和型があり,構文としてレコード構文などが存在します.

代数的データ型は文字通り, 数学における代数の構造を参照にしたデータ型であり,代数的な定義と対応させることで様々なことが可能となります. 代数学を理解するためにはまず,集合論の基礎を理解している必要があります.ここでは,集合論と対応させる形で,代数的データ型とは何であるかを理解することを目指します.

Haskellは代数学の一部である圏論と強い結びつきがあり,プログラムのデータ構造は圏論的に解釈することも可能となります. 特にHaskellの高度な機能, 多相型(ポリモーフィズム),モナド,状態系などは集合論的な理解よりも圏論的な理解のほうが適しています. そこで,ここでは一旦集合論的に概要を把握し,後の章で圏論的な解釈を試みます.

1.1 命題と条件式

集合論的に代数的データ型を解釈するにあたって,数理的な定義の記法に用いる演算子を導入します. 数理的な定義の内,そこで述べられた言説が,「真か偽のいずれかに分類可能とされるもの」を命題といい,条件が与えられた命題を条件式といいいます.

xに関する条件式を P(x)≔*** や Q(x)≔*** と書き，***の部分に,命題が記述されます．

命題の記述には以下の論理演算子が用いられます．

このとき, p(x) \Rightarrow q(x) \Leftrightarrow \neg p(x) \lor q(x) となります.

memo: 全称命題と存在命題 (あとで出てきたときに書く)

1.2 集合

Haskellではデータ型を集合とみなすことができます. Haskellの型はあくまで型であり,厳密には集合ではありません. また,このあと出てくるリストを使った内包表記などの集合論的な書き方も数学における集合ではありません. あくまで類似したものです.

しかし,Haskellを集合とみなすことで,関数型プログラミングや,代数的データ型の意味がより直感的に理解できるようになります. しばらく,集合論とHaskellの対応について考えてみましょう.

特定のモノがそこに｢属するか判定可能なモノの集まり｣を｢集合｣という．

集合の細かな定義は置いておいて,この講義では取り敢えずこのくらいの認識で問題ありません. しかし,ただのモノの集まりではなく,特定のモノがそこに属するかどうかを判定できる必要があるので注意が必要です.

例えば, ｢頭の良い人の集合｣のようなものは,｢頭が良い基準｣が人によって異なるので,集合とはみなせません.

ノーベル賞受賞者の集合,フィールズ賞受賞者の集合,メンサ会員の集合,XX模試の偏差値が70以上の人の集合,特定の科目で85点以上取った人の集合,など,誰でも判別可能な定義が必要です.

私が過去に飼ったことのある犬の種類の集合をMyDogsという名前で呼ぶと,MyDogsに属するモノたちを{ }を使って以下のように書くことができます.

\begin{align*} MyDogs = & \{ GoldenRetriever \\ &, BlackRetriever \\ &, ShetlandSheepdog \\ &, StandardPoodle \\ &, StandardPoodle \} \end{align*}

このとき,GoldenRetrieverや,ShetlandSheepdogはMyDogsの要素であるといい,要素が特定の集合に属するとき,

GoldenRetriever \in MyDogs の様に書きます. 要素に属さないことは Chihuahua \notin MyDogsと書きます.

Haskellにおいて,このようなデータ型を以下の様に定義することが可能です. データ型の宣言は, dataのあとに続いて,データ型の名前(型構築子)を書き,=の後ろにその中身(コンストラクタ/データ構築子)を書きます. 型構築子やデータ構築子は,大文字の英字で始めるのが規則です.

data MyDogs = GoldenRetriever
            | BlackRetriever
            | ShetlandSheepdog
            | StandardPoodle
            | StandardPoodle
            deriving Show

この様にそこに属する要素をすべて書き出す(列挙する)データ型を列挙型といいます.

ちなみに,大文字の英字で始まってさえいればUTF-8の文字や絵文字,記号は使用できるので,以下のような記述も可能ですが,あまりおすすめしません.

data My🐶   = Pゴールデンレトリーバー
            | Pブラックレトリーバー
            | Pシェットランドシープドッグ
            | Pスタンダードプードル
            | Pビーグル
            deriving Show

deriving Showはコンストラクタを文字列に変換する関するshowを自動で導入するための記法です. 自分で定義することも可能ですが,詳細に関しては後ほど扱います.

deriving Showを入れていない状態で

print GoldenRetriever

などを実行すると,以下のエラーがでますが,deriving Showを追加することで,表示することが可能となります.

ghci> :{
ghci| data MyDogs = GoldenRetriever
ghci|             | BlackRetriever
ghci| :}
ghci> print GoldenRetriever

<interactive>:17:1: error: [GHC-39999]
    • No instance for ‘Show MyDogs’ arising from a use of ‘print’
    • In the expression: print GoldenRetriever
      In an equation for ‘it’: it = print GoldenRetriever
ghci> :{
ghci| data MyDogs = GoldenRetriever
ghci|             | BlackRetriever
ghci|             deriving Show
ghci| :}
ghci> print GoldenRetriever
GoldenRetriever

なお, printの実装は

print :: Show a => a -> IO ()
print x = putStrLn (show x)

となっています.

要素が一つも属さない集合を空集合といい,記号\phi または｛｝によって表されます． Haskellでは空集合を表すデータ型としてData.Voidに定義されたVoidが存在します. データ型としてボトム型,記号では⊥で表される場合もあります.

Voidと同じ値を持たないデータ型は,コンストラクタを記述しないことで自分で実装することもできます. 例えば私が犬を今までに一匹もかったことがなければ, MyPet = \phi となり,データ型としては以下のように定義されます. 値が存在しない空集合と対応していることが分かります.

data Mypet

Void型は値が存在しないため実行することはできませんが,コンパイルを通すことはできます. ただし,あまり実用する機会はないので,以下の部分は興味がある人だけ開いて読んでください.

Void型を利用したコードを記述する方法はいくつかありますが, undefinedした実装などが良く用いられます. undefinedは遅延評価を利用した値で,具体的な値や式の記述を省略することができます. 未実装の部分を含めたコードを取り敢えず部分的にコンパイルしてみたい場合や, エラー処理などで利用されます.

以下のコードはコンパイルは通りますが,実行時にはundefined, calledエラーが発生します.


somFunc :: Int -> Int
someFunc = undefined

main = print $ someFunc 1

Void型を利用するケースは非常に限定的ですが,値が無いことを明示的に示したい場合などに利用されます.

{-# LANGUAGE EmptyCase #-}
{-# LANGUAGE EmptyDataDeriving #-}

data Empty deriving Show

head' :: Show a => [a] -> Empty ->  a
head' []     e = case e of
head' (x:[]) _ = x
head' (x:xs) _ = x

main = print $ head' ([]::[Int]) undefined -- >>> undefined, called at

このコードでは, 明示的に先頭の値が存在しないことをEmptyで表し,EmptyDataDeriving拡張でundefinedを評価することでエラーを発生させています.

しかし,こういったパターンでは,以下のerrorによる実装や,後に説明するMaybe型を利用するほうが一般的です.

head'' :: Show a => [a] ->  a
head'' []     = error "Empty List"
head'' (x:[]) = x
head'' (x:xs) = x

main = print $ head'' ([]::[Int]) -- practice: Empty List error, called at

単一の要素だけが存在するデータ型としてUnit型も準備されており,()のような空のタプルとして表されます.

集合の表記法には，外延的表記及び内包的表記という2通りが存在する．外延的表記とは，集合Sに含まれる要素を全て記述する方法で，x,yを要素とする集合を， S={x,y} と書く．集合には順番は関係ないため，{x,y}={y,z}である．また，一つの集合に同じ要素は2つ以上属することができず，{x,x}のような集合は定義できない．

内包的表記とは，その集合に何が属するのかを定義する方法で集合Sに属する要素の集合をｘとすると，ｘがどの集合の要素であるか，どのような条件を持つかなどによって表記する．xの属する集合をX，条件式p(x)とすると，内包的表記では S={x│x∈ X,p(x)} と書かれる．また，内包表記において，関数や定数を定義することも許されており， 関数をf[x]で表すと， S={f(x)|x∈X,f(x)=x+1} のように表記される． 条件の例として，R+を非負の実数としたとき，R+５以下の非負の実数を，以下のように書く． {x|x∈R^+,x≤5} 集合には，集合が属することも可能で，集合SがTに属するときS∈ Tが成り立つ． また，集合Sの要素を幾つか取り出した集合TをSの部分集合といい， T⊂S と表記される． S={x,y,z}のとき，Sの部分集合は {x},{x,y},{x,z},{z,y},{x,y,z},ϕ となる．任意の集合Sに対して ϕ⊂S は成り立つ． また，集合Sの部分集合全体の集合を冪集合といい，pow[S]または2^S と書く． pow[{x,y,z}]={{x},{x,y},{x,z},{z,y},{x,y,z},ϕ}

1.3 型注釈と関数

1.3.1 内包表記

1.4 包含

1.5 積と和

2 代数とクラス

2.1 マグマ

2.2 半群

2.3 モノイド

2.4 群

2.5 リスト

2.6 ツリー

2.7 ネットワーク

3 発展:交換代数

yakagika

ce0f13b2-4a83-4c1c-b2b9-b6d18f4ee6d2