Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

GoでY Combinatorとか不動点関数とかmemoizeとかできたよー

Y Combinatorとは何かという人は, この記事がわかりやすいです. Y コンビネータって何? - IT戦記
JSでは関数の型とかがいらないので, とてもシンプルにY Combinatorが書けます.

var Y = function(f){
  return (function(g){
    return function(m){
      return f(g(g))(m);
    }
  })(function(g){
    return function(m){
      return f(g(g))(m);
    }
  });
}

しかし, Goでは関数の返り値, 引数の型を指定しなければいけません. すると, 上の例に当たるgの引数が再帰的に展開されてしまい, 純粋な関数では書くことが出来ません.
そこで, いったん他のを探すと, の手法ならすぐにいけました.

package main
import "fmt";

type Fix struct {
  f func(int, *Fix) int;
  memo map[int] int;
}

func NewFix(f func(int, *Fix) int) *Fix {
  return &Fix{f, make(map[int]int)};
}

func (fix *Fix) Call(x int, g *Fix) int {
  if item, ok := fix.memo[x]; ok {
    return item;
  }
  fix.memo[x] = g.f(x, g);
  return fix.memo[x];
}

func main() {
  g := NewFix(func(n int, f *Fix) int {
    if n < 2 {
      return n;
    }
    return f.Call(n-1, f) + f.Call(n-2, f);
  });
  fmt.Printf("%d\n", g.Call(40, g));
}

memorizememoizeしているのでとても高速です. しかし, g.Callとやったり第二引数にgをわたしたり, 少しきれいではありません.
しかし, 関数をstructで表すという考え方を用いると, Y Combinator書けるのでは? と考えた結果が以下です.

package main
import "fmt";

type YFix struct {
  f func(*YFix) (func(int) int);
}

func (fix *YFix) Call(g *YFix) (func(int) int) {
  return fix.f(g);
}

func NewY(f func(func(int) int) (func(int) int)) (func(int) int){
  return (&YFix{func(g *YFix) (func(int) int) {
    return func(m int) int{
      return f(g.Call(g))(m);
    }
  }}).Call(&YFix{func(g *YFix) (func(int) int) {
    return func(m int) int{
      return f(g.Call(g))(m);
    }
  }});
}

func main() {
  g := NewY(func (f func(int) int) (func(int) int) {
    return func (n int) int{
      if n < 2 {
        return n;
      }
      return f(n-1) + f(n-2);
    };
  });
  fmt.Printf("%d\n", g(10));
}

NewYがグロイ関数になっていますが, NewYの引数の関数を, intをとりintを返す関数をとり, intをとりintを返す関数を返す関数にし, 作られるgも純粋な関数に出来, とてもきれいに書けるようになりました.

さらにこれにmemoizeを導入します.

package main
import "fmt";

type YFix struct {
  f func(*YFix) (func(int) int);
}

func (fix *YFix) Call(g *YFix) (func(int) int) {
  return fix.f(g);
}

func Memoize(f func(func(int) int) (func(int) int)) (func(func(int) int) (func(int) int)) {
  memo := make(map[int]int);
  return func(g func(int) int) (func(int) int) {
    return f(func(m int) int {
      if item, ok := memo[m]; ok {
        return item;
      }
      memo[m] = g(m);
      return memo[m];
    });
  }
}

func NewY(f func(func(int) int) (func(int) int)) (func(int) int){
  return (&YFix{func(g *YFix) (func(int) int) {
    return func(m int) int{
      return f(g.Call(g))(m);
    }
  }}).Call(&YFix{func(g *YFix) (func(int) int) {
    return func(m int) int{
      return f(g.Call(g))(m);
    }
  }});
}

func main() {
  g := NewY(Memoize(func (f func(int) int) (func(int) int) {
    return func (n int) int{
      if n < 2 {
        return n;
      }
      return f(n-1) + f(n-2);
    };
  }));
  fmt.Printf("%d\n", g(40));
}

とても高速になりました. Memoizeを標準にしたければ, NewYを,

func NewY(f func(func(int) int) (func(int) int)) (func(int) int){
  memo := make(map[int]int);
  return (&YFix{func(g *YFix) (func(int) int) {
    return func(m int) int{
      return f(g.Call(g))(m);
    }
  }}).Call(&YFix{func(g *YFix) (func(int) int) {
    return func(m int) int{
      if item, ok := memo[m]; ok {
        return item;
      }
      memo[m] = f(g.Call(g))(m);
      return memo[m];
    }
  }});
}

としてもいけますね. これで楽しい Y Combinator Life in Go!