Wikipedia

「関数型プログラミング」の版間の差分

履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
編集の要約なし
20行目:
 
'''ラムダ式''' / '''[[無名関数]]''' / '''[[クロージャ]]'''
: ラムダ式と無名関数は同じものである。無名関数はっぱら<code>引数→式</code>（例：<code>x→x+1</code>）の形ように書式で表現され、与えられた引数を加工に作用してた結果値を返す働きをする。書式的特徴から言語によってはラムダ式と呼ばれている。高階関数への引数として使われることが多い。無名関数の式内に外部データを含んだものはクロージャと呼ばれる。クロージャの結果値はその時の外部データの状態に左右される事になる。
 
'''map''' / '''filter''' / '''reduce'''
: リスト処理用の高階関数であり、対象リストと無名第一級関数を引数にする。この第一級関数を作用関数とする。mapはリスト内の各要素を無名作用関数の結果値に置き換える高階関数である。filterはリスト内の各要素を無名作用関数の真偽判定値でにかけて真なら抽出し、その抽出要素のリストを生成する高階関数である。reduceはリスト内の各要素の総和の結果値を生成する高階関数である。reduceの無名作用関数は前要素までの総和と現要素の二引数を取る。総和の和は和に限らず無名作用関数内で好きな計算にできる。
 
'''名前渡し''' / '''[[遅延評価]]'''
: 引数を当てはめた無名関数（コードブロックまたはプロセス）を未計算のまま高階関数に渡せる仕組みを名前渡しという。予め組み立て用意した想定プコードブロセスックを全て高階関数に渡しておき、その高階関数側で必要になったプコードブロセスック結果値だけを求めるようにして計算量を減らすのが主な用途になる。引数確定時とは別タイミングで計算することを遅延評価という。遅延評価では高階関数側で無名関数コードブロックの確定引数を設定し直したり、[[クロージャ]]ならばその時の計算タイミングの外部データ状態に従った結果値を得ることが可能になる。
 
'''[[型推論]]'''
: 型推論は[[静的型付け]]の機能であり、コンパイル時の解析でソースコード内のあらゆる関数適用や変数束縛が求める等価性と値のそれが一致しているかをチェックする。値の等価性は推論的型付け視点の「型」になる。同じ型でなかったら計算不可の型エラーになってコンパイルエラーになる。型の推論はソースコード内のあらゆるプリミティブ記述、データ構築子定義、変数束縛（''Var''）関数定義（''Abs''）関数適用（''App''）等式（''Let''）汎用型構築子定義（''Gen''）実例型構築子宣言定義（''Inst''）といったソースコード内のあらゆる記述ポイント箇所を拾い上げて総合解析するという専用の型推論アルゴリズムで行われる。端的に言うとプリミティブという原子の組み合わせとその写像による変遷を精密に辿ってそれぞれの型を判別していると考えてよい。推論的型付けでは変数/引数/返り値に対する型宣言と型注釈は不要になり、むしろ計算全体の整合性を損ねるものとして倦厭される。[[命令型プログラミング|命令型言語]]（
:手続き型やオブジェクト指向）言語での型推論アルゴリズムは簡素化されているので、型推論の使用対象はローカル変数や引数渡しが中心になる。こその型推論場合の利点は、ローカル変数に型テンプレート的な表現の幅を持たせてソースコードの保守修正作業を容易にすることなどである。従来の型宣言と型注釈を用いる{{仮リンク|明示的型付け|en|Manifest typing|label=}}と、[[型推論]]の共存はC言語世代プログラミングに対する一つのパラダイムシフトでもある。
 
== 特徴 ==
36 ⟶ 37行目:
 
=== 式と関数 ===
関数型プログラムの基本文は[[式 (プログラミング)|式]]（''expression''）である。式は個体（''individual''）である値（''value''）と写像（''mapping''）である関数（''function''）の二つから構成される。関数の定義には[[演算子]]（''operator''）も含まれを兼ねている。値は個体（''individual''）、関数は[[写像]]（''mapping''）とも読み替えられる。値は[[基本データ型]]（プリミティブ）と{{仮リンク|複合データ型（コンポジット）|en|Composite data type|label=}}および[[ラムダ計算]]で言われる変数（''variable''）を意味する。変数は[[束縛変数]]と[[自由変数と束縛変数|自由変数]]を指す。評価（''evaluation''）される前の式は、ラムダ計算で言われるネーム（''name''）と同義になる。ネームは数学上の数式または代数式に相当するものである。式内の変数部分が確定される前の式はラムダ抽象（''abstraction''）と同義になる。式内の変数部分を確定するのはラムダ適用（''application''）と同義になる。この式＝ネームが評価されると値になり、これはラムダ計算で言われる簡約（''reduction''）と同義になる。式は値と同一視されるのですなわち式と値は相互再帰の関係にある。式内の値は他の式の評価値である事があり、その式内にもまた他の値があるといった具合である。この解釈は[[高階論理|高階述語論理]]''と呼ばれる。高階述語論理＝[[高階関数]]の解釈下で引数または返り値として扱われる関数は[[第一級関数]]と呼ばれる。''
 
関数型プログラミングの関数は”関数の型”（''function type''）で分類される[[存在量化子|存在量]]の値である。プログラム的には式に引数を結び付ける機能であり、これは関数を引数に[[写像|適用]]する（''applying a function to an argument''）とされる。関数の式内の仮引数（''parameter''）箇所に渡された実引数（''argument''）が[[パターンマッチング]]手法で当てはめられ、先行（その時''eager''）または遅延（その後''lazy''）タイミングで評価されて結果値が導出される。この仮引数箇所は束縛変数と呼ばれる。関数呼び出し時とは異なるタイミングで内容が決定される変数箇所は自由変数と呼ばれる。letとwhereで特定の式に向けて定義される変数はその式への束縛変数になる。なお関数型パラダイムでの自由変数の意味合いは他の[[宣言型プログラミング|宣言型パラダイム]]とはやや異なっている。関数適用時に用いられる[[パターンマッチング]]手法は、仮引数パターンの[[選言]]的な列挙を可能にしている。このパターンマッチングは”関数の型”に沿った等値性（''equality''）で仮引数と実引数を照合する。更にそれに[[ガード (プログラミング)|ガード]]と呼ばれる値の比較照合と範囲照合を加えることもできる。仮引数が非交和型の場合はその中で列挙されている型との等価性（''equivalent''）でも仮引数と実引数を照合できる。渡される実引数によっては[[ボトム型]]になる関数もありこれは部分関数（''partial function''）と呼ばれる。ボトム型は式ないし関数の評価の失敗した終着点を意味する。演算子はデフォルトの式内容を持ち、その引数が単項演算子なら1個、二項演算子なら2個に限定された関数と同義である。
 
”関数の型”は「第1引数の型→第x引数の型→評価値の型」というように形式化されておりこれはカリー化（''currying''）と呼ばれる。例として関数funcの型を<code>func::A→B→C</code>とするとこの場合、A型値に適用されたfuncは<code>B→C</code>という”関数の型の値”を返す事になり、それをB型値に適用するとC型の評価値が返る事になる。左からの引数にひとつひとつ適用する形にして、<code>B→C</code>のような中間的な”関数の型の値”が導出されるようにする仕組みが関数の[[カリー化]]である。カリー化は写像の[[量化]]（''quantify''）を扱う[[二階述語論理]]の表現手法でもある。カリー化によって関数funcの型は<code>func::A→(B→C)</code>と読み替えられるようになり、この場合にAにのみ適用して<code>B→C</code>という”関数の型の値”のまま保留することは部分適用（''partial application''）と呼ばれる。またカリー化による重要概念に関数合成（''function composition''）がある。これは二項の合成演算子<code>.</code>を関数<code>f::B→C</code>に適用すると<code>(＊→B)→(＊→C)</code>が導出され、それを関数<code>g::A→B</code>に適用すると関数<code>f.g::A→C</code>が導出されるというものである。合成演算子の左側の[[定義域]]と右側の[[値域]]が同じ型の場合のみ合成できる。高階関数的な連結である<code>f(g A)</code>と働きかた的には同じであるが、[[パイプライン処理]]の方に該当する関数連結（関数チェーン）と、カリー化に則った関数合成は異なる概念である。カリー化による部分適用や合成演算子から導出された”関数の型の値”を、任意の変数に束縛して扱うのはポイントフリースタイル（''point-free style''）と呼ばれる。ポイントフリースタイルの変数を値に適用すると、評価された値が返されるかまたは”関数の型の値”が返される事になる。ポイントフリースタイル変数は<code>var value</code>の書式で自身の右の値を暗黙的に引数として取る。ポイントフリースタイルは[[高階述語論理]]と[[存在量化子]]の表現手法でもあり、[[継続渡しスタイル]]にも応用される。引数を部分適用された演算子はセクションと呼ばれてポイントフリースタイルでよく用いられる。[[カリー化]]準拠の”関数の型”は[[型理論]]の指数型（''quotient type''）に分類されるものである。
45 ⟶ 46行目:
 
=== 値とデータ構造 ===
関数型プログラミングの値（''value''）は型（''type''）で分類される[[定数 (プログラミング)|定数]]または[[全称量化子|全称量]]の[[変数 (プログラミング)|変数]]である。これは[[基本データ型]]（プリミティブ）と{{仮リンク|複合データ型（コンポジット）|en|Composite data type|label=}}のいずれかで表現される。プリミティブは数値、論理値、文字値、文字列を指す。コンポシットはプリミティブを任意に組み合わせた複合体であり、例としては[[構造体]]や[[共用体]]などを指す。その組み合わせ方に焦点を当てた用語が[[データ構造]]（''data structure''）である。データ構造という概念には[[再帰]]、[[アノテーション]]、[[ガード (プログラミング)|ガード]]、[[操作的意味論|操作的意味]]といった暗黙情報をも含められるので、コンポジットの具体的形式といった意味で用いられる。関数型言語で用いられるデータ構造の代表例は、[[代数的データ型]]と[[S式]]である。双方ともデータ構築子（''data constructor''）から構築される。まず、プリミティブがデータ構築子によってまとめられる。データ構築子はC言語の構造体/共用体と同性質のものであり、むしろ言い換えるとC言語は直積型のデータ構造を構造体にし、非交和型のデータ構造を共用体にしてペア定義している。データ構築子は入れ子構造と、自身を入れ子にした再帰構造も定義できる。プリミティブとデータ構築子を任意に組み合わせて代数的データ型やS式といったデータ構造が構築される。データ構造内のプリミティブとデータ構築子の組み合わせ方はパターン（''pattern''）と呼ばれる。そのパターンが型になり、パターンの構築が型付けになり、パターンを[[量化]]（''quantify''）すると型付け値になり、これはターム（''term''）と呼ばれる。タームは冒頭の値（''value''）を指す。データ構築子のパターンの末端は必ずプリミティブになるので、パターン内の全てのプリミティブの値を決定することが量化になる。お互いのパターンがマッチするターム同士は等価（''equivalent''）とされる。この等価は同じ型と読み替えてもよい。等価性はあらゆる計算の可否（計算可能性）を決定する。計算とは関数適用または演算子適用を指し、それらが求める仮引数と実引数にするタームが等価であればその計算は成立する事になる。データ構造のパターンは基礎パターンに分解されて解釈される。基礎パターンは[[型理論]]に従って直積型、非交和型、ユニオン型、オプション型、帰納型、ユニット型などに分類されている。
 
[[S式]]は[[二分木|二分木構造]]のデータ構造である。これはコンス（''cons''）と呼ばれる二項のデータ構築子の連結で形成される。コンスは二つの要素を持つ[[タプル]]であり、要素はプリミティブまたは他のコンスのどちらかである。S式はコンスを実行時に連結して任意のパターンを構築する[[動的型付け]]の値である。コンスは要素二つの[[直積集合|直積型]]（''product type''）であり、コンスの連結による要素の並びは[[線形リスト|リスト]]と呼ばれる。コンスの要素は形式化されていない[[非交和|非交和型]]（''sum type''）でもあり、要素の識別はプログラマ側の裁量に委ねられている。コンスの組み合わせによるパターンは任意の識別名に結び付けられる。
71 ⟶ 72行目:
関数型言語の静的型付けでは、性質や役割による[[セマンティクス|意味づけ]]によって値を分類する明示的型付け（''manifest typing''）よりも、計算可能性に基づく[[等価性]]によって値を分類する推論的型付け（''inferred typing''）が主流である。前者の意味づけとはプログラマによる型定義、型宣言、型注釈を指しており人間寄りの視点である。後者の等価性とは値を関数/演算子の引数にできるかどうかの判別を指し、値への関心がそこで計算可能かどうかに絞られているので計算機寄りの視点である。明示的型付けではソースコード上の型宣言と型注釈から値の型が特定されるのに対し、推論的型付けでは[[型推論]]機能で特定される。型推論とは専用のアルゴリズムによる解析によってソースコード内のあらゆる値/変数/引数/返り値それぞれの等価性を導き出す機能である。推論的型付けでは値への関心をその計算可能性に絞っているので、型宣言と型注釈は不要になりまたは相容れないものとなる。例としてint型を型シノニムで金額型と数量型にした場合、明示的型付けではこの両者は区別されるが、推論的型付けでは区別されない。ソースコードの解析でどちらもint型準拠の等価と見られるからである。推論的型付けで値の意味づけ性も表現する場合は、データ構築子で値を包む[[ボックス化]]が用いられる。データ構築子（''data constructor''）は与えられた要素を直積または非交和でまとめるのと同時に[[型理論]]で言われる文脈（''context''）を各要素の等価性に上乗せ付加するものでもある。
 
静的型付けにおける[[データ構造]]のパターン（型）はコンパイル前ないし実行前に全て事前形成される。その実装例である[[代数的データ型]]はデータ構築子の組み合わせでパターンを構築し、パラメトリック多相に基づいて[[ジェネリックプログラミング|総称化]]したパターン内の要素＝型変数を、型構築子への型引数の組み合わせで特定した。''Hindley–Milner''型体系はこのパラメトリック多相に対応した[[型推論]]機能を提供している。型構築子（''type constructor''）は必要とする型引数の個数によって分類され、これは[[カインド (型理論)|カインド]]（''kind''）と呼ばれる。カインドは総称記号である<code>＊</code>の写像で型構築子の型種を表現する。型引数を必要としない型構築子と必要な型引数を全て付与された型構築子はプロパータイプと呼ばれ<code>＊</code>と表現される。プロパータイプは”[[全称量化子|全称量]]の型”である。型引数を1個必要とするものは<code>＊→＊</code>になり、2個必要なら<code>＊→＊→＊</code>になる。これらは”[[存在量化子|存在量]]の型”になる。<code>＊→＊→＊</code>に型引数が1つ付与されると<code>＊→＊</code>になり更に1つ付与すると<code>＊</code>のプロパータイプになる。”全称量化子型”の型付け値（ターム）は普通に扱えるが、”存在量化子型”の型付け値はその一部分が抽象化（大抵は環境依存値と同義）されたままの特別な値と見なされて一定の制限下で扱われる。
 
推論的型付け下の関数の扱いでは、人為的表記による意味づけを重視した記名的型付け（''nominal typing''）が取り入れられており、これで推論的型付けの枠組み内での[[多重定義|関数オーバーロード]]が表現されている。ここでの人為的表記による意味づけとは、型構築子/データ構築子/”関数の型”それぞれのパターン内の型変数に、[[型理論]]で言われる文脈（''context''）を付加することを指している。文脈の付加は制約（''constraint''）と呼ばれる。文脈の付加はアドホック多相と考えられており、代表的な実装例はそれと[[ジェネリックプログラミング]]を組み合わせた[[型クラス]]である。型クラスは、引数/計算値/評価値などを[[総称型]]化したジェネリック関数群の”関数の型”と式内容を定義できる機能であり、同時に推論的型付けと共存する関数オーバーロードの実装と、特定の意味づけ型を扱うための関数モジュールを定義するための手段になっている。型クラスの定義構文では上述のジェネリック関数群が定義され、その型クラス名が文脈記号になる。型構築子の定義に文脈を付加すると、その型クラスのジェネリック関数群にその型構築子＝型を当てはめた関数群がコンパイル時に自動生成される（deriving）。また文脈を付加して当てはめ関数群を自動生成（instance）した上で、その型構築子＝型のための当てはめ関数の式内容を個別定義（where）できる構文もある。この双方がジェネリック関数の特有インスタンス化になる。明示的型付けでは型注釈を付けた引数パターンの列挙というシンプルな手段で関数オーバーロードを表現できるが、推論的型付けでは等価性に上乗せした文脈という二段階の手段が必要になる。記名的型付けと併せた推論的型付けでのオーバーローディング関数の選択決定は、始めに仮引数と実引数の型クラスのみに注目した照合が行われ、次にその型クラスの制約内での型推論照合が行われるという形になる。
93 ⟶ 94行目:
*ファンクタ文脈からの持ち上げ演算子（fmap）は補助的機能。関手に見立てられる。
 
モナド値は付加モナドと自由モナド（Maybe/例外/有限リストモナドなど）以外では、実質的に存在量の値になるので普通の値のように扱うことは出来ない。ただし付加/自由モナドでも参照透過性を維持するためには存在量と同等に扱う必要が出てくる。<code>return</code>を基本値に適用してモナド値を表現することからモナド処理は始まる。基本値とは扱うモナドに合わせた任意の値である。そのモナド値は圏としてのユニークIDを持つことになる。ここで基本値を<code>A</code>としそのモナド値を<code>MA</code>とする。<code>MA</code>にbindを適用して<code>(A→MB)→MB</code>という写像を導出する。その写像は先の<code>MA</code>と同じ圏IDを備えたものになる。その写像をモナド関数<code>(A→MB)</code>に適用すると、そのモナド関数内では渡された<code>A</code>やその他の値などに<code>return</code>を適用して表現されるモナド値の圏IDは<code>MA</code>のもので共通化される。モナド関数内においての<code>return</code>は基本値をモナド値に代入する機能と見てよい。<code>return</code>は用途別関数にそれぞれラッピングされて使われるのが普通である。空引数からモナド値を表現する<code>return</code>もありこれはモナドプリミティブ（''monadic primitive''）と呼ばれ、この場合はモナド値の圏IDが暗黙引数になっている。モナド値はファイルハンドルのようなものと考えると分かりやすくなり、モナド値を直接引数にできる専用関数も存在する。モナド関数内ではモナド値から基本値を取り出す演算子が有効になる。それは<code>A←MA</code>のように表現されてコモナド（''comonad''）と呼ばれる機能になる。このコモナドは実際には空のモナド値の圏に移す関手である。抽出した基本値からの処理の中で再度<code>return</code>が行われる。モナド関数は自己関手内容に見立てられているので、その中では<code>return</code>の繰り返しによる事実上の再代入処理が許されている。その論理的な辻褄合わせの要点になる<code>bind</code>の正当性および計算可能性を表現するためにファンクタ則とモナド則の等式がプログラム内で定義されている。ここでいわゆる圏論の知識が必要になるがその説明は先送りする。モナド関数はモナド値を返しそれに再度<code>bind</code>を適用できるのでこれがモノイドを意味している。モナド関数の外での<code>return</code>は毎時ユニークな圏IDのモナド値を表現するので同じ基本値でもその都度異なる圏が表現される事になり、これが[[自然変換]]（[[関手圏]]の[[射 (圏論)|射]]）演算子の呼称由来になっている。
 
モナドは'''ファンクタ'''（''functor''）の派生文脈にされることが多いが、これは<code>bind</code>を形成するクライスリ射と<code>join</code>の合成の持ち上げ（関手）に<code>fmap</code>が使われるからである。ファンクタ文脈は関手<code>fmap</code>を持つ。そのままファンクタの機能名で呼ばれることが多い<code>fmap</code>は、関数<code>(A→B)</code>から関数<code>(TA→TB)</code>を導出する関手＝関数である。この関数は<code>TA</code>に適用できて<code>TB</code>を導出できる。<code>T</code>は基本値を包むコンテキストまたはコンテナでありその代表例はリストである。基本値に対する作用をコンテキストで拡張解釈できるのがファンクタの利点である。例えば基本値への+1という作用をリストのコンテキストで拡張解釈するのはリストの全要素に+1するという意味になる。これはリストをそのまま計算対象にできる利便性に繋がる。ファンクタの派生文脈に'''アプリカティブ'''（''applicative''）がある。アプリカティブは、ファンクタのコンテキストに包まれた関数を「コンテキストに包まれた先頭引数→コンテキストに包まれた残り引数＆評価値」という1引数の関数に変換する演算子<code><*></code>を持つ。<code><*></code>は<code>F(A→B)</code>から<code>(FA→FB)</code>を導出する演算子である。<code>F</code>はコンテキスト、<code>(A→B)</code>は元の関数、<code>(FA→FB)</code>は1引数の関数である。この<code>FB</code>は多相であり実際は値<code>F＊</code>関数<code>F(＊→＊)</code> 関数<code>F(＊→＊→＊)</code>などになっているのでそれに<code><*></code>を再び適用できる。アプリカティブは、2個以上の引数の関数をファンクタするための機能と考えてよい。2個以上の引数の関数は<code>fmap</code>でそのまま持ち上げられないのでアプリカティブ関手の<code>pure</code>が用いられる。これは<code>A→FA</code>と表現され<code>A</code>が関数、<code>F</code>がコンテキストである。<code>pure</code>によって好きな引数個数の関数をコンテキストで包み<code><*></code>をそれに適用して導出された関数を<code>FA</code>に適用できる。アプリカティブ関手<code>pure::A→FA</code>とモナドのη自然変換演算子<code>return::A→MA</code>は同じ働きに見えるが、前者は関数（関数の型の値）を純粋に持ち上げるだけの[[関手]]なのに対して、後者は持ち上げる関手を毎時垂直合成していく[[関手圏]]の[[射 (圏論)|射]]（[[自然変換]]）であるという性質上の違いがある。
「https://ja.wikipedia.org/wiki/関数型プログラミング」から取得