blog.ryota-ka.me

代数的データ型と初等代数学

「関数プログラミングとはなんですか?」と問われたときには「デ,データファースト……(震え声)」と答えることが多いのだが,実際 Haskell や OCaml などの言語を特徴付けるものとして,代数的データ型 (Algebraic Data Type; ADT) の存在は無視できないだろう.その有用性ゆえに,近年では新たな言語の策定の際にその概念が輸出され,Rust や Swift などの言語にも採用されている.

「代数的データ型とはなんですか?」と問われたときには——問われたことがないのでわからないのだが——おもむろに ghci か utop を立ち上げて,解説を始めるのではないかと思う.ひとしきり解説をした後,「つまり直積の直和なんですよ〜🙌✨」と言って話を締めくくるだろう.

int 型や float 型など,「メモリ上の表現」という計算機の気持ちに極めて寄り添ったプリミティヴなデータ型や,オブジェクトがヒープに展開された先のアドレスを保持する参照型にしか馴染みがないプログラマにとっては,データ型の定義に「代数」などという仰々しい概念が登場するのは不思議に思われるかもしれない.しかし,代数的データ型自体の有用性は,少しプログラムを書けばわかる*1はずであるし,そもそも「代数」などという難しい言い方をしなければ,自然数どうしの足し算や掛け算,指数の計算などは,小中学校での教育を通じて万人が既に知っており,日頃から親しんでいるはずである.この記事では,人々がよく知る計算の上に成り立つ法則と,代数的データ型との類似性を示すことで,代数的データ型に親しみを持ってもらうことを目的としている.この記事を読み終えた頃には,「Option[T] とか T? とかいう型は T+1T+1 とでも書かれるべきものなのか〜」という理解がなされることが期待される.

基礎的な Haskell の読み書きと,概ね中学校から高校1年生くらいで習う程度の数学の知識があれば読み進められるはずである.また,この記事では再帰的に定義されたデータ型は扱わない*2

続きを読む