challenge 不動点演算子

不動点演算子とは、関数を引数に取り、その関数の不動点を返すような関数です。 つまり、不動点演算子である関数gが関数fを引数に取るとき、 f(g(f)) = g(f) となります。

お題は不動点演算子を実装することです。(Yコンビネータを実装しても結構ですが、それ以外でも、コンビネータになっていなくてもOKとします)

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();
    }
}

Index

Feed

Other

Link

Pathtraq

loading...