翻訳と辞書
Words near each other
・ Yu・A・ガガーリン記念コムソモリスク=ナ=アムーレ航空機製造合同
・ YŪ'S GOODS
・ YŪKI
・ Y∀IBA
・ Y∞Y動画
・ Yの悲劇
・ Yウィング
・ Yウイング
・ Yウムラウト
・ Yカード
Yコンビネータ
・ Yコンビネータ (企業)
・ Yコンビネーター
・ Yシャツ
・ Yショップ
・ Yナンバー
・ Yネット
・ Yボソン
・ Yロウ
・ Y・A・ガガーリン


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

Yコンビネータ : ミニ英和和英辞書
Yコンビネータ[ちょうおん]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

コンビネータ : [こんびねーた]
 (n) combinator, (n) combinator
: [ちょうおん]
 (n) long vowel mark (usually only used in katakana)

Yコンビネータ ( リダイレクト:不動点コンビネータ ) : ウィキペディア日本語版
不動点コンビネータ[ふどうてんこんびねーた]

不動点コンビネータ(ふどうてんコンビネータ、、不動点結合子、ふどうてんけつごうし)とは、与えられた関数不動点(のひとつ)を求める高階関数である。不動点演算子(ふどうてんえんざんし、)、パラドキシカル結合子()などとも呼ばれる。ここで関数''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.