Monad in C++
這些整理一下丟到嵐達網好了...
不過我現在累翻了，晚點再整理 >< 現在只是筆記下來，
因為不想一直留在 tab 上。
FC++: Functional Programming in C++
Monad 的部份在這 FC++ Monads
==
這幾天老林丟太多東西，消化不完 XD
很多都覺得值得筆記一下...
What have you found for these years?
2009-12-12
Subscribe to:
Post Comments (Atom)
favorite albums
All texts are licensed under CC Attribution 3.0
6 retries:
就以我這篇回應做為我這四天來練習 Combinator 的總結吧
雖然已確定手工 Y-Combinator in C++ (no lazy) 就算
compile 過，在 runtime 也會掉進 infinite loop；
但 Z-Combinator 確實可以做出來，雖然我對 Y -> Z 的
expansion 還不太知道轉換的推導，不過大體上就是用
lambda 多抽一層出來就對了，也知道最後不會變成 infinite
的關鍵在哪了。
以下就是貨真價實的手工 C++0x Z-Combinator，
除了 C++0x lambda 與 std::function 以外沒用別的東西，
要多些 return type 的話把 Z 改成 template，define 代換
應該就好了。
#define FT std::function
typedef FT＜int(int)＞ F;
struct Untyped {
＿＿Untyped( FT＜F(Untyped)＞ lamb ):lamb_(lamb){}
＿＿F operator()(Untyped xprime) const {
＿＿＿＿return lamb_(xprime);
＿＿}
＿＿FT＜F(Untyped)＞ lamb_;
};
F Z(FT＜F(F)＞ f){
＿＿Untyped temp(
＿＿＿＿[f](Untyped x) -> F {
＿＿＿＿＿＿return f(
＿＿＿＿＿＿＿＿[x](int y) -> int {
＿＿＿＿＿＿＿＿＿＿return x(x)(y);
＿＿＿＿＿＿＿＿}
＿＿＿＿＿＿);
＿＿＿＿});
＿＿return temp(temp);
}
/* in main */
FT＜F(F)＞ almost_fac = [](F f) -> F {
＿＿return [f](int n)->int{
＿＿＿＿if( n == 0 ) return 1;
＿＿＿＿return n*f(n-1);
＿＿};
};
cout << Z(almost_fac)(10) << endl; //3628800
我看到底線時真的愣了幾秒 XDDDDD
那個 Untyped 我覺得滿漂亮的 XD
（以下補上 im 上聊到的：）
Y 與 Z 的差別：
不過經你這麼一說，我細看了一下 wikipedia 上的 Y 和 Z
Y = λf. (λx. f (x x)) (λx. f (x x))
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
真的是 x x => λy. x x y
eta-conversion
http://en.wikipedia.org/wiki/Eta_expansion#.CE.B7-conversion
f = λx. f x (whenever x does not appear free in f.)
只要他是 curried function, 看來肯定是 equivalent
但不是 curried function 就不是很確定...? 可能還要再查和想一下。
我還得用全形的＜＞ orz
可以用 < 和 >
還有 是空格
很麻煩沒錯啦... XD
在純 lambda calculus 裡面任何東西都是 lambda expression, 所以把 f 變成 \y -> f y 是不會有 type error 的.. 不知道你講的是不是這個？
主要是在想 C++ 的部份，不過經此一提忽然想到...
\y -> f y 在只吃一個 arg 的狀況下，type 應該是相同的。
所以上面這樣寫，應該只能吃一個 arg, 需要多個大概就像是：
\y... -> f y...
y... 則表示有一個以上的 arg forward 過去。
這樣似乎就沒有 curry 不 curry 的問題了 @@
Post a Comment
Note: Only a member of this blog may post a comment.