不動点演算子
Posted feedbacks - Java
わざわざJavaで書く意味がないですね(笑)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | public class FixedPointOperator {
// 任意の関数型 T を定義します
abstract class T {
abstract T apply(final T arg);
}
// 整数型を定義します
class Int extends T {
int val;
Int(int val) { this.val = val; }
// 整数型の apply が呼ばれることはありません
T apply(final T arg) { throw new RuntimeException(); }
}
// 不動点オペレータを定義します
// Y = (g=>(s=>g (x=>(s s) x))(s=>g (x=>(s s) x)))
// ------------ ここを tmp2 としています
// ------------------- ここを tmp1 としています
final T Y = new T() {
T apply(final T g) {
final T tmp1 = new T() {
T apply(final T s) {
final T tmp2 = new T() {
T apply(final T x) {
return s.apply(s).apply(x);
}
};
return g.apply(tmp2);
}
};
return tmp1.apply(tmp1);
}
};
// 階乗を求める関数です (サンプル)
// factRec = (f=>(x=>(if x = 0 then 1 else x * (f (x - 1)))))
final T factRec = new T() {
T apply(final T f) {
return new T() {
T apply(final T x) {
int i = ((Int) x).val;
if (i == 0) {
return new Int(1);
} else {
return new Int(i * ((Int) f.apply(new Int(i - 1))).val);
}
}
};
}
};
// 不動点オペレータ Y を factRec に適用して再帰的関数を作成
// ためしに fact(5) を計算します
public void exec() {
T fact = Y.apply(factRec);
Int five = new Int(5);
Int result = (Int) fact.apply(five);
System.out.println("fact(" + five.val + ") = " + result.val);
}
public static void main(String args[]) {
new FixedPointOperator().exec();
}
}
|

matarillo
#5680()
Rating2/4=0.50
不動点演算子とは、関数を引数に取り、その関数の不動点を返すような関数です。 つまり、不動点演算子である関数gが関数fを引数に取るとき、 f(g(f)) = g(f) となります。
お題は不動点演算子を実装することです。(Yコンビネータを実装しても結構ですが、それ以外でも、コンビネータになっていなくてもOKとします)
see: Wikipedia
[ reply ]