翻訳と辞書
Words near each other
・ 不動池
・ 不動沢橋
・ 不動滝
・ 不動滝 (秩父市)
・ 不動滝 (高森町)
・ 不動点
・ 不動点の作図法
・ 不動点コンビネータ
・ 不動点定理
・ 不動点演算子
不動点結合子
・ 不動王生霊返し
・ 不動産
・ 不動産に関する資格一覧
・ 不動産の鑑定評価に関する法律
・ 不動産アナリスト
・ 不動産カウンセラー
・ 不動産キャリアパーソン
・ 不動産コンサルティング技能登録者
・ 不動産テック


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

不動点結合子 : ウィキペディア日本語版
不動点コンビネータ[ふどうてんこんびねーた]

不動点コンビネータ(ふどうてんコンビネータ、、不動点結合子、ふどうてんけつごうし)とは、与えられた関数不動点(のひとつ)を求める高階関数である。不動点演算子(ふどうてんえんざんし、)、パラドキシカル結合子()などとも呼ばれる。ここで関数''f''の不動点とは、''f''(''x'') = ''x''を満たすような''x''のことをいう。
すなわち高階関数''g'' が不動点コンビネータであるとは、
:任意の関数''f'' に対し、''p'' = ''g''(''f'')とすると, ''f''(''p'') = ''p'' が成立する
事を指す。
不動点コンビネータの定義は、任意の関数''f'' に対し、
:f(\mathbf(f))=\mathbf(f)
が成立する事であるとも言い換えられる。
第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。〔This terminology appear to be largely folklore, but it does appear in the following:
* Trey Nash, ''Accelerated C# 2008'', Apress, 2007, ISBN 1590598733, p. 462--463. Derived substantially from Wes Dyer 's blog (see next item).
* Wes Dyer Anonymous Recursion in C# , February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.〕〔The If Works Deriving the Y combinator , January 10th, 2008〕
不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算()においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。'g'' が不動点コンビネータであるとは、
:任意の関数''f'' に対し、''p'' = ''g''(''f'')とすると, ''f''(''p'') = ''p'' が成立する
事を指す。
不動点コンビネータの定義は、任意の関数''f'' に対し、
:f(\mathbf(f))=\mathbf(f)
が成立する事であるとも言い換えられる。
第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。〔This terminology appear to be largely folklore, but it does appear in the following:
* Trey Nash, ''Accelerated C# 2008'', Apress, 2007, ISBN 1590598733, p. 462--463. Derived substantially from Wes Dyer 's blog (see next item).
* Wes Dyer Anonymous Recursion in C# , February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.〕〔The If Works Deriving the Y combinator , January 10th, 2008〕
不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算()においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。' が不動点コンビネータであるとは、
:任意の関数''f'' に対し、''p'' = ''g''(''f'')とすると, ''f''(''p'') = ''p'' が成立する
事を指す。
不動点コンビネータの定義は、任意の関数''f'' に対し、
:f(\mathbf(f))=\mathbf(f)
が成立する事であるとも言い換えられる。
第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。〔This terminology appear to be largely folklore, but it does appear in the following:
* Trey Nash, ''Accelerated C# 2008'', Apress, 2007, ISBN 1590598733, p. 462--463. Derived substantially from Wes Dyer 's blog (see next item).
* Wes Dyer Anonymous Recursion in C# , February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.〕〔The If Works Deriving the Y combinator , January 10th, 2008〕
不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算()においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。'g''(''f'')とすると, ''f''(''p'') = ''p'' が成立する
事を指す。
不動点コンビネータの定義は、任意の関数''f'' に対し、
:f(\mathbf(f))=\mathbf(f)
が成立する事であるとも言い換えられる。
第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。〔This terminology appear to be largely folklore, but it does appear in the following:
* Trey Nash, ''Accelerated C# 2008'', Apress, 2007, ISBN 1590598733, p. 462--463. Derived substantially from Wes Dyer 's blog (see next item).
* Wes Dyer Anonymous Recursion in C# , February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.〕〔The If Works Deriving the Y combinator , January 10th, 2008〕
不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算()においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。'(''f'')とすると, ''f''(''p'') = ''p'' が成立する
事を指す。
不動点コンビネータの定義は、任意の関数''f'' に対し、
:f(\mathbf(f))=\mathbf(f)
が成立する事であるとも言い換えられる。
第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。〔This terminology appear to be largely folklore, but it does appear in the following:
* Trey Nash, ''Accelerated C# 2008'', Apress, 2007, ISBN 1590598733, p. 462--463. Derived substantially from Wes Dyer 's blog (see next item).
* Wes Dyer Anonymous Recursion in C# , February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.〕〔The If Works Deriving the Y combinator , January 10th, 2008〕
不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算()においては、ハスケル・カリーY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。
== 不動点コンビネータによる再帰の実現 ==
不動点コンビネータにより、第一級関数をサポートしているプログラミング言語において、明示的に再帰を書かずに再帰を実現する為に用いる事ができる。なお、一般にそういった言語では普通に再帰が使えるので、プログラミングにおいてはパズル的なテクニック以上の意味は無い。一方、循環なく関数の意味を定義する(できる)、ということは、計算理論の上では重要である。
まず、再帰関数の性質を簡単に振り返り、記号をいくつか定義する。関数''a'' が再帰的に定義されているとき、''a''の定義式は何らかの高階関数''U'' を用いて、
: a(x) = U(a,x) ...(1)
と書ける。たとえば''a(x)'' がxの階乗を計算する関数である場合、Uとして
: U(f,x) = \begin 1 & \text x=0 \\ x
* f(x-1) &\text\end
を取る事ができる。上述のように定義された''U'' が(1)を満たすのは明らかであろう。
''U'' を用いて高階関数V
: V~:~f \mapsto U(f,\cdot) ...(2)
と定義する。
(すなわち''V''は関数''f'' を入力として受け取ると
関数「x \mapsto U(f,x)」を出力する高階関数である。
ラムダ計算の用語で言えば、''V'' は''U'' のカリー化\lambda f.~ (\lambda x.~ U)にあたる。)
''V'' の定義より、V(f)はそれ自身関数であり、任意の''x'' に対し、
: V(f)(x)=U(f,x) ...(3)
が成り立つ。ここでV(f)(x)は関数V(f)に''x'' を入力したときの値。
さて、''g'' を不動点コンビネータとするとき、不動点コンビネータの定義より特に、
\mathbf(V)は''V'' の定義域の元である事が分かる。
''V'' の定義域は関数の集合だったので、これはすなわち\mathbf(V)はそれ自身関数である事を意味する。
この関数\mathbf(V)が(1)式で定義された再帰関数''a'' と一致する事を示す事ができる(後述)。
よって以下のようにすれば不動点コンビネータ''g'' で再帰関数''a'' を実現できる事になる:
# ''U'' のプログラムを書く。
# ''V'' を(2)式のように定義し、a=\mathbf(V)とする。'g'' を不動点コンビネータとするとき、不動点コンビネータの定義より特に、
\mathbf(V)は''V'' の定義域の元である事が分かる。
''V'' の定義域は関数の集合だったので、これはすなわち\mathbf(V)はそれ自身関数である事を意味する。
この関数\mathbf(V)が(1)式で定義された再帰関数''a'' と一致する事を示す事ができる(後述)。
よって以下のようにすれば不動点コンビネータ''g'' で再帰関数''a'' を実現できる事になる:
# ''U'' のプログラムを書く。
# ''V'' を(2)式のように定義し、a=\mathbf(V)とする。' を不動点コンビネータとするとき、不動点コンビネータの定義より特に、
\mathbf(V)は''V'' の定義域の元である事が分かる。
''V'' の定義域は関数の集合だったので、これはすなわち\mathbf(V)はそれ自身関数である事を意味する。
この関数\mathbf(V)が(1)式で定義された再帰関数''a'' と一致する事を示す事ができる(後述)。
よって以下のようにすれば不動点コンビネータ''g'' で再帰関数''a'' を実現できる事になる:
# ''U'' のプログラムを書く。
# ''V'' を(2)式のように定義し、a=\mathbf(V)とする。'g'' で再帰関数''a'' を実現できる事になる:
# ''U'' のプログラムを書く。
# ''V'' を(2)式のように定義し、a=\mathbf(V)とする。' で再帰関数''a'' を実現できる事になる:
# ''U'' のプログラムを書く。
# ''V'' を(2)式のように定義し、a=\mathbf(V)とする。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「不動点コンビネータ」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Fixed-point combinator 」があります。



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.