12/03/20 00:15:14.64
もう少し言えば
チャーチ数は >>836 のリンク先のように自然数の「構造」を関数で表現したものだ
例えば自然数の 2 は、何かに関数を2回適用するという構造として表現している
しかし、他の関数型言語のことは知らんが、
少なくとも Haskell では関数を使って何かの「構造」を表現する事はできない
Haskell の関数は、あくまで何かを計算する事しかできない
関数では不可能な構造を表現するために代数データ型が存在している
例えば何かに関数を2回適用したのか、それとも3回適用したのかを知るには、
その関数適用の構造ではなく、適用した結果に対して自然数の2や3を対応付けるしかない
もちろん、2回適用したものと3回適用したものとの和を計算するのも、
その関数適用の構造そのもので和を計算するのではなく、
関数を適用した結果が対応する「値」に対して和を計算するしかない
関数を適用した結果を代数データ型というある種の構造を表現する値に対応付けることはできる
その方法で構造を自然数に対応付けるのが >>836 の例なのだが、
これは関数で自然数の構造を表現しているのではなく、
あくまで代数データ型で自然数の構造を表現しているのだから、
もはやチャーチ数とは呼べない（構造の形自体は似たように作れるが）
よって、チャーチ数の表現およびその上での演算ができるのが最低限と言われると、
少なくとも Haskell は関数型ではなくなってしまうと私は思う
838:デフォルトの名無しさん
12/03/20 00:22:50.19
template<class> struct F;
template<class> struct Count;
template<class type> struct Count< F<type> >
{
enum{ value = Count< type >::value + 1 };
}
template<class type> struct Count< void >
{
enum{ value = 0 };
};
Count< F< F< F< F<void> > > >::value == 4;
C++のtemplateの方がまだ関数型なのか？
839:デフォルトの名無しさん
12/03/20 00:26:26.44
あ、間違えた
× template<class type> struct Count< void >
○ template<> struct Count< void >
840:デフォルトの名無しさん
12/03/20 02:59:07.51
>>837
まさか、昔書いたコードを引っ張り出すことになるとわw
-- 自然数を定義
data NaturalNum = Zero | PlusOne NaturalNum
deriving (Eq,Ord,Show,Read)
-- 加算を定義
Zero +^ n = n
m +^ Zero = m
m +^ n = inc m +^ dec n
-- 減算を定義
Zero -^ n = n
m -^ Zero = m
m -^ n | m == n = Zero
m -^ n = dec m -^ dec n
-- インクリメント（１＋）を定義
inc n = PlusOne (n)
-- デクリメント（１－）を定義
dec (PlusOne (n)) = n
-- 自然数を独自自然数へ変換
int2NaturalNum 0 = Zero
int2NaturalNum n = PlusOne (int2NaturalNum (n-1))
-- 独自自然数を自然数へ変換
naturalNum2int Zero = 0
naturalNum2int n = 1 + naturalNum2int (dec n)
841:デフォルトの名無しさん
12/03/20 03:04:19.80
あ、関数そのものを自然数として表現できるか？か・・・
うーん、時間が有るとき挑戦してみよう
842:デフォルトの名無しさん
12/03/20 03:17:44.71
ぱっと思いついただけだから、違うかもだけど・・・
Prelude> let null = 0
Prelude> let f = (1+)
Prelude> f $ f $ f null
3
843:デフォルトの名無しさん
12/03/20 07:42:39.05
お前ら、チャーチ数をぜんぜん理解していないなwww
844:デフォルトの名無しさん
12/03/20 08:27:05.60
まあ代数データ型で定義されるデータコンストラクタも関数の一種ですけどね
静的型なので普通の関数とは区別されてますが
845:デフォルトの名無しさん
12/03/20 10:21:15.73
>>842
そうやって表現した自然数3の「構造」と、
同じように表現した自然数4の「構造」とを足して、
自然数7という数値ではなく、自然数7という「構造」がラムダ式のみで得られるか
ということだよ
チャーチ数がラムダ式で表現する自然数7という「構造」は、
λf x. f (f (f (f (f (f (f x)))))) だ
846:デフォルトの名無しさん
12/03/20 10:42:53.44
型無しラムダ計算でしかできない技法を、型付きラムダ計算ベースのプログラミング言語で
できないぞやーいやーい、と言っているお子様のいるスレはこちらですか？
847:デフォルトの名無しさん
12/03/20 11:32:41.98
>>846
私は Haskell を揶揄しているつもりは毛頭ない
Haskell の他言語に対する利点欠点など、今回の話では何も関係ないからどうでいい
チャーチ数の定義が Wikipedia に載っているものであるならば
「１引数関数 f と任意の x を受け取り、f を x に n 回適用する『関数』を返す関数」
Haskell でその定義どおりにチャーチ数およびの上での演算は表現できないのではないか
したがって、関数型言語ならばそれができて当然とは言えないのではないか
と私は言っている
更に、そもそも Haskell では関数を使って構造を定義することはできないと私は考える
また >>846 に反論するが、
たとえ Haskell が今の形を保ったまま型無し言語に変わったとしても、
依然として Haskell の関数で構造を表現する事はできないのではないだろうか
Haskell だと関数の構造は隠されており、何回適用したかは外から見えない
値構築子も関数の一種だという意見も一方ではあり、
たとえば >>840 で表現できるというと言う人もいるだろうが、
それは上記の定義における「任意の x」を「ある特定の x」に限定したものではないだろうか
もちろんそれは、関数が何回適用されたかの数を保存する構造を持ったある x だ
848:デフォルトの名無しさん
12/03/20 12:17:06.20
＞更に、そもそも Haskell では関数を使って構造を定義することはできないと私は考える
まぁ、ランクＮ多相使えばできるけどな。
URLﾘﾝｸ(d.hatena.ne.jp)
849:デフォルトの名無しさん
12/03/20 13:06:30.40
>>848
申し訳ない
言語としてのHaskellを考える時は Haskell 2010 Language Report を参照している
URLﾘﾝｸ(www.haskell.org)
それはそれとして、言語拡張を使った >>848 の例は面白そうなので、
これでチャーチ数およびその上での計算ができるか検証してみる
850: [―{}@{}@{}-] デフォルトの名無しさん
12/03/20 22:38:25.55
newtype使ってこう書くのって上手くいく? (newtypeを使うのが許されるのなら)
それともどこかに落し穴がある?
newtype MyNum a r = MyNum { unNum :: ((MyNum a r -> r) -> r -> r) }
-- 続きはgistで
URLﾘﾝｸ(gist.github.com)
少なくとも+ - * == factは関数とMyNumだけで書けてるっぽい。Intへの変換も可能。
851:デフォルトの名無しさん
12/03/20 23:35:48.23
>>850
上手くいくというのを、チャーチ数の定義と同義だという意味で言ってるのなら、
○○的帰納法で試しかめてみれば良いんじゃないか
0 の時にチャーチ数の定義と同義か確かめる
x の時にチャーチ数の定義と同義だとして x+1 の時にチャーチ数の定義と同義か確かめる
852:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/02 17:34:49.72
URLﾘﾝｸ(www.amazon.co.jp) これ誰か読んでみた人いる？
ドーバーだけに安いんだけどな。元は1989年の本。
853:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/02 17:36:16.25
中身をチラミしてみると、lispとMLで解説してるみたいだね。
854:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/02 18:10:39.12
昔読んだよ。
型なしのλ計算に、かなり素朴な方法で複合型を導入してる。
だから厳密さはないが、それなりに面白い。
ただのPostscript版があるからちょっと読んでみれば？
>>853
いや、最後の二章でMLとLiispを扱ってるだけ。
855:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/02 18:37:12.66
Lambda-Calculus and Combinators: An Introduction はお奨めでしょうか？
look insideしたら簡単に書いてくれてる気がする
856:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/05 12:50:00.85
>>854
情報さんくす。 読んでみます。
857:営利利用に関するLR審議中＠詳細は自治スレへ
12/04/05 13:53:20.55
>>855
それは 「Hindley and Seldin」とも呼ばれたりする定番本です。
簡単ってことはないけど、手元に一冊あれば今後も色々と参照すること間違いない本。
この本の内容が簡単という人は、この世界に進んだほうがいいと思われ