クラなんとか or くらなんとか or cla なんとかの日記

Scala で Church 数を書いてみた(途中)

Scala, SICP

Scala 座があるので，Scala を使ってみようということで，

Church 数を書いてみた．が，書けなかったという話．

コメントアウトしてある型パラメータ版だと，

Nothing は，A に入りません．って怒られるのです．

これはどうやって解決したらいいんですかね？

識者の意見を求む．

Permalink | コメント(0) | トラックバック(0) | 08:02

Java 版チャーチ数を書いてみた(改)

Java, Scala, Clojure, SICP

ということで，以前書いたJava 版チャーチ数を更新しました．

以前のバージョンだと戻り値の型がjava.lang.Integer 決め打ちだったのが

気になっていたので，それをtype variable にして外に追い出しました．

簡単な説明

• 無名オブジェクトを作ってクロージャとして使っている - http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AD%E3%83%BC%E3%82%B8%E3%83%A3#Java
• インターフェイス F を引数と戻り値の両方に使っている．
  • Church :: (a -> a) -> a -> a なので，第一引数とそれを渡してからの戻り値が同じ型(a -> a)

ついでに，以下の4つのパターンでテストを書いてみました．

• Test::More(Perl)
• JUnit(Java)
• ScalaTest(Scala)
• test-is(Clojure)

気付いたこととしては，Clojure は，型がゆるい所為か

Java ソースに型変数部分を導入しても型変数部分を変更する必要が無かった．

Clojure 版はソースも短い．

Scala は，型LOVE なら，記述力も高いし気持いい．

とあいえ，型変数の<> を [] で書く．型を後に書くとか，

Java と混ぜて書くのは訳わからんくなりそう．

Clojure だと，違うところは違い，同じところは同じなので，その辺があまり気にならない気がした．*1

調べ足りないこと，Java でクロージャを作ろうとすると final が必要になるのは何故？

参考

• http://gist.github.com/306300

スーパーpre 記法が，Clojure に対応していて良かった．-> d:id:hatenadiary:20100219:1266571864

ちぇりお！

以下ソース

Main.java

class Main {
    public static void main(String[] args) {
        Church zero = Church.ZERO;
        Church one = zero.inc();
        Church two = one.inc();
        Church three = one.plus(two);

        F<Integer> to_i = new F<Integer>() {
                public Integer proc(Integer x) {
                    return Integer.valueOf(x.intValue() + 1);
                }
            };

        Integer number_zero = new Integer(0);

        System.out.println(zero.proc(to_i).proc(number_zero));
        System.out.println(one.proc(to_i).proc(number_zero));
        System.out.println(two.proc(to_i).proc(number_zero));
        System.out.println(three.proc(to_i).proc(number_zero));
    }
}

F.java

public interface F<T> {
    public T proc(T x);
}

Church.java

// proc :: (a -> a) -> a -> a
// (a -> a)         is F (interface)
// proc F :: a -> a is F
// (a)              is T (anonymous type)
abstract public class Church {
    abstract public <T> F<T> proc(F<T> f);

    public static Church ZERO = new Church() {
            public <T> F<T> proc(F<T> f) {
                return new F<T>() {
                    public T proc(T x) {
                        return x;
                    }
                };
            }
        };

    public Church inc() {
        return Church.inc(this);
    }

    public Church plus(final Church n) {
        return Church.plus(this, n);
    }

    public static Church inc(final Church n) {
        return new Church() {
            public <T> F<T> proc(final F<T> f) {
                return new F<T>() {
                    public T proc(T x) {
                        return f.proc(n.proc(f).proc(x));
                    }
                };
            }
        };
    }

    public static Church plus(final Church m, final Church n) {
        return new Church() {
            public <T> F<T> proc(final F<T> f) {
                return new F<T>() {
                    public T proc(T x) {
                        return n.proc(f).proc(m.proc(f).proc(x));
                    }
                };
            }
        };
    }
}

ChurchTest.java - JUnit 版テスト

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;

import org.junit.runner.JUnitCore;

import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Ignore;
import org.junit.Test;

public class ChurchTest {
    private Church zero = null;
    private Church one = null;
    private Church two = null;
    private Church three = null;
    private F<Integer> to_i = null;
    private Integer i_zero = null;

    @Before
    public void before() {
        this.zero = Church.ZERO;
        this.to_i = new F<Integer>() {
            public Integer proc(Integer x) {
                return Integer.valueOf(x.intValue() + 1);
            }
        };
        this.one = zero.inc();
        this.two = one.inc();
        this.three = one.plus(two);
        this.i_zero = new Integer(0);
    }

    @After
    public void after() {
        this.zero = null;
        this.one = null;
        this.two = null;
        this.three = null;
        this.to_i = null;
        this.i_zero = null;
    }

    @Test
    public void testToI() {
        assertThat(this.to_i.proc(i_zero), is(new Integer(1)));
    }

    @Test
    public void testZero() {
        assertThat(to_i(this.zero), is(0));
    }

    @Test
    public void testOne() {
        assertThat(to_i(this.one), is(1));
    }

    @Test
    public void testTwo() {
        assertThat(to_i(this.two), is(2));
    }

    @Test
    public void testThree() {
        assertThat(to_i(this.three), is(3));
    }

    int to_i(Church n) {
        return n.proc(this.to_i).proc(this.i_zero).intValue();
    }

    public static void main(String[] args) {
        JUnitCore.main(ChurchTest.class.getName());
    }
}

ChurchTestSuite.scala - ScalaTest 版

import org.scalatest.FunSuite
 
class ChurchTestSuite extends FunSuite {
  val zero = Church.ZERO;
  val one = zero.inc;
  val two = one.inc;
  val three = two.plus(one); // 2 + 1
  val to_i = new F[java.lang.Integer] {
    def proc(x : java.lang.Integer) : java.lang.Integer = {
      java.lang.Integer.valueOf(x.intValue + 1)
    }
  }

  test("inc is increment") {
    assert(to_i.proc(0) === 1)
  }
 
  test("zero:Church convert to zero:Num (Church.ZERO)") {
    assert(c_to_i(zero) === 0)
  }

  test("one:Church convert to one:Num (Church.inc)") {
    assert(c_to_i(one) === 1)
  }

  test("two:Church convert to two:Num (Church.inc for incremented)") {
    assert(c_to_i(two) === 2)
  }

  test("three:Church convert to three:Num (Church.plus)") {
    assert(c_to_i(three) === 3)
  }

  // helper method
  def c_to_i(n : Church) : Int = {
    n.proc(to_i).proc(0).intValue
  }
}

test.clj - test-is 版

(ns test
  (:import F Church)
  (:use clojure.contrib.test-is))

(def to_i (proxy [F] [] (proc [x] (+ x 1))))
(def zero (Church/ZERO))
(def one (. zero inc))
(def two (. one inc))
(def three (. one (plus two)))

(defn c_to_i [n]
  (.. n (proc to_i) (proc 0)))

(deftest test-to_i
  (is (= 1 (. to_i (proc 0)))))

(deftest test-zero-for-static_value
  (is (= 0 (c_to_i zero))))

(deftest test-one-for-inc
  (is (= 1 (c_to_i one))))

(deftest test-two-for-inc-with-incremented-value
  (is (= 2 (c_to_i two))))

(deftest test-three-for-plus
  (is (= 3 (c_to_i three))))

(run-tests)

Permalink | コメント(0) | トラックバック(0) | 21:07

Java でチャーチ数を書いてみた(途中)

Java, SICP

ということで，Java を勉強し直すということにして，チャーチ数を書いてみた．

色々納得がいってないので後で書き直す．

interface F {
    public Integer proc(Integer x);
}

abstract class Church {
    abstract public F proc(F f);

    public static Church ZERO = new Church() {
            public F proc(F f) {
                return new F() {
                    public Integer proc(Integer x) {
                        return x;
                    }
                };
            }
        };

    public Church inc() {
        return Church.inc(this);
    }

    public Church plus(final Church n) {
        return Church.plus(this, n);
    }

    public static Church inc(final Church n) {
        return new Church() {
            public F proc(final F f) {
                return new F() {
                    public Integer proc(Integer x) {
                        return f.proc(n.proc(f).proc(x));
                    }
                };
            }
        };
    }

    public static Church plus(final Church m, final Church n) {
        return new Church() {
            public F proc(final F f) {
                return new F() {
                    public Integer proc(Integer x) {
                        return n.proc(f).proc(m.proc(f).proc(x));
                    }
                };
            }
        };
    }
}

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;

import org.junit.runner.JUnitCore;

import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Ignore;
import org.junit.Test;

public class ChurchTest {
    private Church zero = null;
    private Church one = null;
    private Church two = null;
    private Church three = null;
    private F to_i = null;
    private Integer i_zero = null;

    @Before
    public void before() {
        this.zero = Church.ZERO;
        this.to_i = new F() {
            public Integer proc(Integer x) {
                return Integer.valueOf(x.intValue() + 1);
            }
        };
        this.one = zero.inc();
        this.two = one.inc();
        this.three = one.plus(two);
        this.i_zero = new Integer(0);
    }

    @After
    public void after() {
        this.zero = null;
        this.one = null;
        this.two = null;
        this.three = null;
        this.to_i = null;
        this.i_zero = null;
    }

    @Test
    public void testToI() {
        assertThat(this.to_i.proc(i_zero), is(new Integer(1)));
    }

    @Test
    public void testZero() {
        assertThat(to_i(this.zero), is(0));
    }

    @Test
    public void testOne() {
        assertThat(to_i(this.one), is(1));
    }

    @Test
    public void testTwo() {
        assertThat(to_i(this.two), is(2));
    }

    @Test
    public void testThree() {
        assertThat(to_i(this.three), is(3));
    }

    int to_i(Church n) {
        return n.proc(this.to_i).proc(this.i_zero).intValue();
    }

    public static void main(String[] args) {
        JUnitCore.main(ChurchTest.class.getName());
    }
}

• http://gist.github.com/306300

Permalink | コメント(0) | トラックバック(0) | 22:36

sicplite #8 にいってきた

study, SICP

• 遅刻をしました
  • 正直 Erlang Super Lite と間違えていた(来週です
    • もう脳からして Erlang 脳になったと思ったのに(自己満足
• 2.43 を考えていた
• accumlate-n が Ruby の Enumerable::zip っぽい
  • accumulate-n を勘違いしていた → tree をmap っぽくするものだと
    • 普通に map (fold f) . zip でした
• queens は，内部実装が違うくても他が違わないということでFA？
  • accumulate-n の関数引数の戻り値の型は，初期値の型と同じになる
• Ruby の zip は，オブジェクト指向なのでレシーバ重視なのだな

Haskell だと accumulate-n は，こんな感じか？(脳内コンパイルなので動くか知りません

accumulate :: (a -> b -> a) -> a -> [b] -> a
accumulate = foldl

accumulate_n :: (a -> b -> a) -> a -> [[b]] -> [a]
-- accumulate_n f ini xs | any null xs = []
--                       | otherwise = accumulate f ini (map head xs) 
--                                     : accumulate_n f ini (map tail xs)
accumulate_n f ini xs = map (\xs -> foldl f ini xs) (tr xs)
  where tr xs | any null xs = []
              | otherwise   = map head xs : tr (map tail xs)

Haskell 実行例

> map reverse $ accumulate_n (\i r->r:i) [] [[1,2,3],[4,5,6],[7,8,9],[10,11,12]]
[[1,4,7,10],[2,5,8,11],[3,6,9,12]]

Ruby 版

irb> r=[];[1,2,3].zip([4,5,6],[7,8,9],[10,11,12]) {|v| r << v};r
=> [[1, 4, 7, 10], [2, 5, 8, 11], [3, 6, 9, 12]]
irb> r=[];[1,2,3].zip([4,5,6],[7,8,9],[10,11,12]) {|v| r << v.inject(0){|i,e|i+e}};r
=> [22, 26, 30]

Permalink | コメント(0) | トラックバック(0)

sicplite #7 にいってきた

study, SICP

• 超ムーミン
• 口がlite
• でも，やるときにはやる
• fold で書くとか
• 個人的に Gauche の fold の引数と Haskell の foldl の引数の順序が違う気がする(未検証
• accumulator って，fold-left だよね
• fold って，inject?
  • inject (Ruby) は，fold-left だと思う．
  • PHP の array_reduce って，何だっけ？(PHP おもしろい発言

なので，こんな感じに書ける

(define (reverse xs)
   (fold cons (list) xs))
(define (deep-reverse tree)
   (fold (lambda (x i) (cons (if (pair? x) (deep-reverse x) x) i)) (list) tree))

fold-left と fold-right は，展開したのを考えるとわかりやすいと自分では思っている．

(fold-left f i [list a b c])
; => (f c (f b (f a i))) ; 展開した形

(fold-right f r [list a b c])
; => (f a (f b (f c r))) ; 展開した形

引数の作用順が違う．

#!/usr/bin/env gosh
(fold       (lambda (x i) (cons x i)) (list) (list 1 2 3))
; => (3 2 1)
(fold-right (lambda (x r) (cons x r)) (list) (list 1 2 3))
; => (1 2 3)

引数の順序をわかりやすくするために，わざとlambda 式で書いてある．

ということで，Ruby の inject は，fold-left ってことで

irb(main):001:0> [1,2,3].inject([]) {|i,x| i << x}
=> [1, 2, 3]

参考

• http://href.spiritloose.net/?Prelude%20foldl
• http://www.ruby-lang.org/ja/man/html/Enumerable.html
• http://practical-scheme.net/gauche/man/gauche-refj_102.html#SEC295
• http://d.hatena.ne.jp/blanketsky/20071129/1196329379
• http://rainyday.blog.so-net.ne.jp/2007-10-14-1

Permalink | コメント(0) | トラックバック(0)