What have you found for these years?

2009-12-12

Monad in C++

這些整理一下丟到嵐達網好了...
不過我現在累翻了,晚點再整理 >< 現在只是筆記下來,
因為不想一直留在 tab 上。
FC++: Functional Programming in C++

Monad 的部份在這 FC++ Monads

==
這幾天老林丟太多東西,消化不完 XD
很多都覺得值得筆記一下...

6 retries:

老林 said...

就以我這篇回應做為我這四天來練習 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

godfat 真常 said...

我看到底線時真的愣了幾秒 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 就不是很確定...? 可能還要再查和想一下。

老林 said...

我還得用全形的<> orz

godfat 真常 said...

可以用 &lt; 和 &gt;
還有 &nbsp; 是空格

很麻煩沒錯啦... XD

scm said...

在純 lambda calculus 裡面任何東西都是 lambda expression, 所以把 f 變成 \y -> f y 是不會有 type error 的.. 不知道你講的是不是這個?

godfat 真常 said...

主要是在想 C++ 的部份,不過經此一提忽然想到...

\y -> f y 在只吃一個 arg 的狀況下,type 應該是相同的。
所以上面這樣寫,應該只能吃一個 arg, 需要多個大概就像是:
\y... -> f y...
y... 則表示有一個以上的 arg forward 過去。

這樣似乎就沒有 curry 不 curry 的問題了 @@

Post a Comment

All texts are licensed under CC Attribution 3.0