すぐに忘れる脳みそのためのメモ

ラベル 総称型 の投稿を表示しています。すべての投稿を表示

2010年8月30日月曜日

Java で型変数を利用して Cons , Nil クラスによるリスト表現 – map, filter, foldr, foldl の実装

「Haskell でリストに対する関数を考えるときの視点」のつづき

Haskell のリストに対応した Java クラス

前回は Haskell のリストに対応したクラスを定義し、リストの大きさを返すメソッド length を実装した。

gist: 556957 - GitHub (前回より少し変更)

このクラスを使い、map, filter, foldr, foldl の実装を考える。

ここで予め Main クラスで利用するリストを作成しておく。以降この変数 list を使う。

IList<Integer> list = new Nil<Integer>().cons(4).cons(3).cons(2).cons(1);
System.out.println(list);    // 1 2 3 4

累積変数を使った length メソッド

まずは、前回実装した length 関数を、末尾再帰で定義したときのような格好の実装を追加してみる。

Cons クラス...

    public int length(int acc) {
        return this.xs.length(acc + 1);
    }

累積変数 acc を導入し、そこへ要素の数を累積させる。

リストの末尾の Nil クラスでは、累積変数を返す。

    public int length(int acc) {
        return acc;
    }

Main クラスでこれを使ってみる。

        System.out.println(list.length(0));  // 4

map

次に、リストの要素に対して関数を適用する map 関数に相当するメソッドを定義する。

Haskell での map 関数の型は、

map :: (a -> b) -> [a] -> [b]

第1引数は、要素を別の型の値へ変換する関数。

Java では「関数」を関数の引数へ渡すことができないので、オブジェクトを代わりに渡し Strategy パターンで対応。オブジェクトの実装するインターフェイスを IUnaryOp として以下のように宣言し、利用するときはインターフェイスを実装した匿名クラスを作成する。

public interface IUnaryOp<A,B> {
    public B apply(A a);
}

apply 関数は、引数に A 型の値を与えると B 型の値が返ってくる。これは Haskell の map 関数の第1引数 (a –> b) に相当。

IList インターフェイスに map メソッドの宣言を追加。

    public <B> IList<B> map(IUnaryOp<A, B> f);

上記の型変数 B は、このインターフェイスを実装したクラスを生成するときではなく、このメソッドを使うときに決まるので、メソッドで型変数を宣言する。 ( cf. Java の型変数とイレイジャ )

上記に伴ない Cons クラスで map メソッドを実装。

    public <B> IList<B> map(IUnaryOp<A, B> f) {
        return this.xs.map(f).cons(f.apply(this.x));
    }

Nil クラスにも map メソッドを実装。

    public <B> IList<B> map(IUnaryOp<A, B> f) {
        return new Nil<B>();
    }

これを Main クラスで使用する。

// map ： 要素を 2 倍する
System.out.println(list.map(
        new IUnaryOp<Integer, Integer>() {
            public Integer apply(Integer a) {
                return a * 2;
            }
        }));     // 2 4 6 8

filter

filter 関数は述語を与え、リストから要素を抽出する関数。

Haskell の filter 関数の型は、

filter :: (a -> Bool) -> [a] -> [a]

第1引数は、ある型の値を渡すと Bool 型を返す述語。

先ほどの map メソッドのように、filter 関数の第1引数に相当する述語に対応したメソッドを持つオブジェクトのインターフェイスを IPredicate とし、メソッドを宣言。

public interface IPredicate<A> {
    public boolean apply(A a);
}

apply メソッドは、引数に型 A の値を与えると boolean が返る。これは Haskell の filter 関数の第1引数 (a –> Bool) に相当する。

IList インターフェイスに filter メソッドの宣言を追加。

    public IList<A> filter(IPredicate<A> p);

上記に伴ない Cons クラスで filter メソッドを実装。

    public IList<A> filter(IPredicate<A> p) {
        return p.apply(this.x) == true
                ? this.xs.filter(p).cons(this.x)
                : this.xs.filter(p);
    }

Nil クラスにも filter メソッドを実装。

    public IList<A> filter(IPredicate<A> p) {
        return new Nil<A>();
    }

Main クラスでこれを使う。

// filter ： 偶数を抽出
System.out.println(list.filter(new IPredicate<Integer>() {
    public boolean apply(Integer p) {
        return p % 2 == 1;
    }
}));     // 1 3

foldr

forldr はリストの右側から二項演算子により特定の型の値に畳み込む関数。

Haskell の foldr の型は、

foldr :: (a -> b -> b) -> b -> [a] -> b

これまでと同様、foldr の第1引数の関数に相当するメソッドを持つオブジェクトを生成するためにインターフェイス IBinaryOp1 を宣言。今回は二項演算子なので、引数が一つ増える。

public interface IBinaryOp1<A, B> {
    public B apply(A a, B b);
}

apply メソッドの引数には型 A の値と型 B の値を与えると型 B の値が返る。これは Haskell の foldr 関数の第1引数の型 (a –> b –> b) に相当する。

IList インターフェイスに foldr メソッドの宣言を追加。このとき Haskell の foldr の型と比較しながら宣言を考えるとよい。

    public <B> B foldr(IBinaryOp1<A, B> f, B z);

上記に伴ない Cons クラスに foldr メソッドを実装。

    public <B> B foldr(IBinaryOp1<A, B> f, B z) {
        return f.apply(this.x, this.xs.foldr(f, z));
    }

Nil クラスにも foldr メソッドを実装。

    public <B> B foldr(IBinaryOp1<A, B> f, B z) {
        return z;
    }

これを Main クラスで使う。

// foldr : 要素を足し合わせる
System.out.println(list.foldr(new IBinaryOp1<Integer, Integer>() {
    public Integer apply(Integer a, Integer b) {
        return a + b;
    }
}, 0));                 // 10

// foldr : リストのコピー
System.out.println(list.foldr(
        new IBinaryOp1<Integer, IList>() {
            public IList apply(Integer a, IList b) {
                return b.cons(a);
            }
        },
        new Nil()));    // 1 2 3 4

foldl

foldr が右から畳み込むのに対して、foldl は左から畳み込む関数。

Haskell の foldl 関数の型は、

foldl :: (a -> b -> a) -> a -> [b] –> a

よく見ると foldr と型が少し違うのがわかる。

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr のときと同様に、第1引数の関数に相当するメソッドを持つオブジェクトのインターフェイスを IBinaryOp2 とする。

public interface IBinaryOp2<A, B> {
    public A apply(A a, B b);
}

apply メソッドは引数型 A の値と型 B の値を与えると、型 A の値が返る。これは Haskell の foldl の第1引数 (a –> b –> a) に相当する。

IList インターフェイスに foldr メソッドを追加。ただし、foldr のときのように Haskell の型と完全に同じようになっていないことに注意。理由は、Cons クラスで実装したところを見るとわかる。

    public <B> B foldl(IBinaryOp2<B, A> f, B z);

上記に伴ない Cons クラスに foldr メソッドを実装。

    public <B> B foldl(IBinaryOp2<B, A> f, B z) {
        return this.xs.foldl(f, f.apply(z, this.x));
    }

特に第1引数が

IBinaryOp2<A, B>

ではなく、

IBinaryOp2<B, A>

であることに気をつける。

後者の場合、IBinaryOp2 インターフェイスに照らし合わせると、メソッド apply の型は次のようになる。

public B apply(B b, A a)

このように型変数名が変わっても本質的な意味は同じ。

しかし、これを Cons クラスのメソッドのシグニチャに用いると意味がそれぞれ異なる。理由は、Cons クラスが持つ型変数が A であり、この A と上記 apply メソッドの型変数名 A が一致するので、これによりメソッド全体において型変数 A の意味が定まるから。 (多分… ^^; 色々と試して動いたのがこれだったので、後付けで理由を考えた。)

Nil クラスにも foldr メソッドを定義。

    public <B> B foldl(IBinaryOp2<B, A> f, B z) {
        return z;
    }

これを使ってみる。

// foldl ： 要素を足し合わせる
System.out.println(list.foldl(
        new IBinaryOp2<Integer, Integer>() {
            public Integer apply(Integer a, Integer b) {
                return a + b;
            }
        },
        0));       // 10

// foldl ： 要素を掛け合せる
System.out.println(list.foldl(
        new IBinaryOp2<Integer, Integer>() {
            public Integer apply(Integer a, Integer b) {
                return a * b;
            }
        },
        1));       // 2

メソッドチェーン

最後に上記 map, filter, foldr でメソッドチェーン。

// メソッドチェーン : filter => map => foldr ：
System.out.println(list.filter(new IPredicate<Integer>() {
    public boolean apply(Integer p) {
        return p % 2 == 0;     // 偶数を抽出
    }
}).map(new IUnaryOp<Integer, Integer>() {
    public Integer apply(Integer a) {
        return a * 3;          // 3 をかける
    }
}).foldr(new IBinaryOp1<Integer, Integer>() {
    public Integer apply(Integer a, Integer b) {
        return a * b;          // 掛け合わせる
    }
}, 1));     // 72

結論は、こんなゴチャゴチャしたコードは書きたくないということで。(+_+)

型を書くのが面倒なので型推論してくれぇ～。

てゆうか、これからの実用所はやっぱ Scala っすか ?

ここまでのコード

gist: 556957 – GitHub

クラス図。(メソッドにおける型変数を無理矢理書いてしまったけれど。)

Java の型変数とイレイジャ - 具体的な型の指定を忘れずに

2010年2月27日土曜日

Java の型変数とイレイジャ - 具体的な型の指定を忘れずに

Java の型変数に慣れるための練習。

例えば、変数を『箱』に見たて、「箱の中の値」と「別の何らかの値」を引数として与えると、二つをくっつけて返す takeOut メソッドがあるとする。

takeOut (箱の中の値, 別の何らかの値) => 2 つをくっつけた値

ただし、この関数は次の制約を満さなければならないという条件付きで。

takeOut メソッドが返す値の型は、箱の中身の型ではなく、もう一方の「別の何らかの値」の型と一致する。

箱を int 型として、もう一方の値を int 型としたときのイメージは以下の通り。

同じく箱を int 型として、もう一つの値を String 型としたときのイメージ。

実装。

public class Main00 {

    public static void main(String[] args) {
        int box = 100;
        System.out.println(box);                 // 100
        System.out.println(takeOut(box, 200));   // 300
        System.out.println(takeOut(box, "円"));  // 100円
    }

    static int takeOut(int box, int val) {
        return box + val;
    }

    static String takeOut(int box, String str) {
        return box + str;
    }
}

特定の型に依存している箇所

上記の実装は特定の型に依存している。型に依存している部分は次の 3 つ。

箱の中身 … (A)
別の何らかの値 (takeOut メソッドの第2引数) … (B)
上記 (A), (B) をくっつける演算子(関数)

これらが可変になるようにしたい。

クラスで型変数を宣言

まずは、箱をクラスとして実装し、中身を保持するための型変数を導入。型変数により箱はどんな型でも受け入れることができるようになり、入れた中身の型に応じたメソッドを作成可能。

「箱に入れた中身を取り出す」だけの takeOut メソッドから実装する。

クラスで型変数を宣言し、その型変数を「箱の中身」を保持するためのプライベート変数の型として宣言し、takeOut メソッドはその型変数を返すようにする。中身は箱を生成するときに渡すとするなら、

public class Box<A> {

    private A contents;

    Box(A contents) {
        this.contents = contents;
    }

    A takeOut() {
        return this.contents;
    }
}

メソッドで型変数を宣言

先ほどの takeOut メソッドを見ると、「箱の中身」と「別の何らかの値」をくっつける関数は 2 項演算子 `+’ だった。これを、与えられる値の型に応じて、適切な 2 項演算子を適用できるように変更したい。ただし、先ほどの制約は守ることにする。

takeOut メソッドが返す値の型は、箱の中身の型ではなく、もう一方の「別の何らかの値」の型と一致する。

これをイメージしたのが下図。「箱の中身」を型変数 A で、「もう一つの値」に対応したものを型変数 B とし、二項演算子を f で表現した。

ところで、Java は関数を直接メソッドに渡せないので、Strategy パターンでオブジェクトを渡す必要がある。このとき、2項演算子を適用するメソッドを apply とし、インターフェイスを IBinaryOp とする。 apply メソッドの第1引数は「箱の中身」、第2引数は「別のもう一つの値」が渡されるとするなら、

public interface IBinaryOp<A, B> {
    public B apply(A a, B b);
}

第2引数と返り値は、型変数 B で一致させることにより型チェックができる。

これで Box クラスの takeOut メソッドを次のように定義できる。

<B> B takeOut(IBinaryOp<A, B> f, B b) {
 return f.apply(this.contents, b);
}

型変数 B の具体的な型は、Box クラスの生成時に決まるのではなく、このメソッドを使うときに決まる。よって、メソッドにおいて型変数を宣言。もし、これをクラスの型変数としてしまうと、Box の生成時に型を指定しなければならず、また、そのときに指定した型に固定されてしまう。

ここまでのコード。

Box.java : gist: 316379 – GitHub
IBinaryOp.java : gist: 316378 - GitHub

型変数に具体的な型を指定して使う

Box クラスを作成できたので、Main クラスの main メソッドで使ってみる。はじめは箱に入れた値を取り出すだけ。

Box<Integer> box1 = new Box<Integer>(100);
System.out.println(box1.takeOut());            // 100

Box クラスをインスタンス化する文において、型宣言と new の双方において具体的な型 <Integer> を指定することを忘れずに。

匿名クラスでインターフェイスを実装したクラスを作成

次に、「箱から取り出した値」と「別のもう一つの値」を引数に取るメソッドを作成する。これは匿名クラスを利用した。

System.out.println(box1.takeOut(
        new IBinaryOp<Integer, Integer>() {
            public Integer apply(Integer a, Integer b) {
                return a + b;
            }
        },
        200));                                 // 300

先ほどと同じく、IBinaryOp インターフェイスを実装するクラスをインスタンス化するときに具体的な型の指定を忘れずに。これによりコンパイル時に型チェックがされる。

ところで、takeOut 関数の引数と返り値の型は以下の通りだった。

<B> B takeOut(IBinaryOp<A, B> f, B b) {

上例の場合、型変数 B に Integer 型が対応する。よって、takeOut の第2引数の値を文字列にすると、「型が違うよ」とコンパイラが間違いを指摘してくれる。具体的な型を指定してないと型チェックはされず、メソッドでキャストをしなければならない。

もし、 takeOut の第2引数の値を文字列にしたいなら、この定義では以下のように IBinaryOp インターフェイスを実装したクラスのオブジェクトを生成するときに具体的な型として String を指定。

System.out.println(box1.takeOut(
        new IBinaryOp<Integer, String>() {
            public String apply(Integer a, String b) {
                return a + b;
            }
        },
        "円"));                                // 100円

型変数のメリット

当然ながら、Box クラスで型変数を利用しているので、箱の中身の型が違っていても問題ない。main メソッドにおいて、中身を文字列に変更して使うなら、

Box<String> box2 = new Box<String>("百");
System.out.println(box2.takeOut());              // 百

System.out.println(box2.takeOut(
        new IBinaryOp<String, String>() {
            public String apply(String a, String b) {
                return a + b;
            }
        },
        "円"));                                  // 百円

NetBeans でメソッドの引数と返り値の型を補完

ちなみに、Netbeans を使っている場合、IBinaryOp インターフェイスを実装するときに、

new IBinaryOp<Integer, Integer>()

を入力した後、

メニューより「ソース > コードを修正...」を選択するか、コードの左に出るランプのようなアイコンをクリックすると、「すべての抽象メソッドを実装」がポップアップし、

選択すると型に応じた空のメソッドが生成される。

コード全体

ここまでのコード。

型のイレイジャに注意

ところで、型変数を利用したクラスを使うのは、特定の型に依存した実装ではなく、色々な型に対応でき、かつ、コンパイル時に型のチェックができるからだった。ただし、型変数があるにも関わらず、型を指定せずにコードを書くことも可能。これは、Java総称型メモ(Hishidama's Java Generics Memo) によると、

総称型として定義されているクラスから型パラメータを除去したクラスを「型のイレイジャ（型消去：type erasure）」と呼ぶ。…

つまり「List<T>」に対し「List」、「Map<K, V>」に対し「Map」が“イレイジャ”。

例えば、先ほどの例で Box クラスのオブジェクトを生成するとき、型宣言で具体的な型を指定しなかったとする。

Box box1 = new Box<Integer>(100);

Box クラスの takeOut メソッドは IBinaryOp の型変数 B が決まると、第2引数と返り値の型が決まるのだった。

<B> B takeOut(IBinaryOp<A, B> f, B b) {

しかし、この場合 box1 の型変数が指定されてないためなのか(?)、コンパイラが型チェックをしてくれない。(イレイジャは関係している型変数のチェックを無効にしてしまうのかな？)

System.out.println(box1.takeOut(
        new IBinaryOp<Integer, Integer>() {
            public Integer apply(Integer a, Integer b) {
                return a + b;
            }
        },
        "hoge"));

上記は実行した段階で「キャストできません」と例外が投げられる。

Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

具体的な型の指定を忘れるとコンパイル時にチェックされない。ジェネリクスの恩恵を受けるために忘れないように。

Haskell の場合

同じ意味合いのコードをHaskell で実装するなら、

data Box a = Box a deriving Show

takeOut         :: Box a -> a
takeOut (Box x) = x

takeOutWith             :: (a -> b -> b) -> b -> Box a -> b
takeOutWith f z (Box x) = x `f` z

main = do let box1 = Box 100
              box2 = Box "Hyaku"
          print $ takeOut box1                                -- 100
          print $ takeOutWith (+) 200 box1                    -- 300
          print $ takeOutWith (\a b -> show a ++ b) "En" box1 -- "100En"
          print $ takeOutWith ((++).show) "En" box1           -- "100En"

          print $ takeOut box2      -- "Hyaku"
          print $ takeOutWith (++) "En" box2     -- "HyakuEn"

う～ん、シンプル。

Java の方は本当にあれでいいのかなぁ。。 (+_+) 実はここで書いた例は、Java で Cons クラスをベースにリストを作り、その上で foldr, foldl に相当するメソッドを実装したらどうなるか試していたとき、型チェックがされなくておかしなぁ～と思い、よりシンプルな例にして試したもの。上記の不自然に見える制約は、foldr, foldl に与える 2項演算子における型と同じようにしたかったので、そのようにした。

Java で型変数を利用して Cons , Nil クラスによるリスト表現 – map, filter, foldr, foldl の実装

参考サイト

Java総称型メモ(Hishidama's Java Generics Memo)

登録: 投稿(Atom)

すぐに忘れる脳みそのためのメモ

2010年8月30日月曜日

Java で型変数を利用して Cons , Nil クラスによるリスト表現 – map, filter, foldr, foldl の実装

Haskell のリストに対応した Java クラス

累積変数を使った length メソッド

map

filter

foldr

foldl

メソッドチェーン

ここまでのコード

関連記事

2010年2月27日土曜日

Java の型変数とイレイジャ - 具体的な型の指定を忘れずに

特定の型に依存している箇所

クラスで型変数を宣言

メソッドで型変数を宣言

型変数に具体的な型を指定して使う

匿名クラスでインターフェイスを実装したクラスを作成

型変数のメリット

NetBeans でメソッドの引数と返り値の型を補完

コード全体

型のイレイジャに注意

Haskell の場合

関連記事

参考サイト

人気の投稿

すぐに忘れる脳みそのためのメモ

2010年8月30日月曜日

Java で型変数を利用して Cons , Nil クラスによるリスト表現 – map, filter, foldr, foldl の実装

Haskell のリストに対応した Java クラス

累積変数を使った length メソッド

map

filter

foldr

foldl

メソッドチェーン

ここまでのコード

関連記事

2010年2月27日土曜日

Java の型変数 とイレイジャ - 具体的な型の指定を忘れずに

特定の型に依存している箇所

クラスで型変数を宣言

メソッドで型変数を宣言

型変数に具体的な型を指定して使う

匿名クラスでインターフェイスを実装したクラスを作成

型変数のメリット

NetBeans でメソッドの引数と返り値の型を補完

コード全体

型のイレイジャに注意

Haskell の場合

関連記事

参考サイト

人気の投稿

Java の型変数とイレイジャ - 具体的な型の指定を忘れずに