Skip to content

Instantly share code, notes, and snippets.

@jutememo
Created August 30, 2010 03:05
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jutememo/556957 to your computer and use it in GitHub Desktop.
Save jutememo/556957 to your computer and use it in GitHub Desktop.
public class Cons<A> implements IList<A> {
/**
* リストの先頭要素
*/
private A x;
/**
* リストの残りの要素
*/
private IList<A> xs; // 型変数を忘れないように!
public Cons(A x, IList<A> xs) {
this.x = x;
this.xs = xs;
}
public Cons<A> cons(A x) {
return new Cons<A>(x, this);
}
public int length() {
return 1 + this.xs.length();
}
public int length(int acc) {
return this.xs.length(acc + 1);
}
@Override
public String toString() {
return this.x.toString() + " " + this.xs.toString();
}
public <B> IList<B> map(IUnaryOp<A, B> f) {
return this.xs.map(f).cons(f.apply(this.x));
}
public IList<A> filter(IPredicate<A> p) {
return p.apply(this.x) == true
? this.xs.filter(p).cons(this.x)
: this.xs.filter(p);
}
public <B> B foldr(IBinaryOp1<A, B> f, B z) {
return f.apply(this.x, this.xs.foldr(f, z));
}
public <B> B foldl(IBinaryOp2<B, A> f, B z) {
return this.xs.foldl(f, f.apply(z, this.x));
}
}
public interface IBinaryOp1<A, B> {
public B apply(A a, B b);
}
public interface IBinaryOp2<A, B> {
public A apply(A a, B b);
}
public interface IList<A> {
/**
* リストの先頭に要素 a を追加する
* @param a 追加する要素
* @return リスト
*/
public IList<A> cons(A x);
/**
* リストの要素数を返す
* @return リストの要素数
*/
public int length();
/**
* リストの要素数を返す
* (末尾再帰に相当)
* @param acc 累積変数
* @return リストの要素数
*/
public int length(int acc);
/**
* 要素にオブジェクト f のメソッドを適用する
* @param f 要素を変換するメソッドを持つオブジェクト
* @return 要素の型が B であるリスト
*/
public <B> IList<B> map(IUnaryOp<A, B> f);
/**
* リストからオブジェクト p のメソッド(述語)により要素を抽出する
* @param p 述語
* @return リスト
*/
public IList<A> filter(IPredicate<A> p);
/**
* リストの要素をオブジェクト f のメソッドにより右から畳み込む
* @param f 二つの要素を畳み込みこむための二項演算子
* @param z 最初に畳み込むための値
* @return 畳み込んだ値
*/
public <B> B foldr(IBinaryOp1<A, B> f, B z);
/**
* リストの要素をオブジェクト f のメソッドにより左から畳み込む
* @param f 二つの要素を畳み込みこむための二項演算子
* @param z 最初に畳み込むための値
* @return 畳み込んだ値
*/
public <B> B foldl(IBinaryOp2<B, A> f, B z);
}
public interface IPredicate<A> {
public boolean apply(A a);
}
public interface IUnaryOp<A,B> {
public B apply(A a);
}
public class Main {
public static void main(String[] args) {
// 型変数を忘れないように!
IList<Integer> list = new Nil<Integer>().cons(4).cons(3).cons(2).cons(1);
System.out.println(list);
System.out.println(list.length());
System.out.println(list.length(0));
// map : 要素を 2 倍する
System.out.println(list.map(
new IUnaryOp<Integer, Integer>() {
public Integer apply(Integer a) {
return a * 2;
}
}));
// filter : 偶数を抽出
System.out.println(list.filter(new IPredicate<Integer>() {
public boolean apply(Integer p) {
return p % 2 == 1;
}
}));
// foldr : 要素を足し合わせる
System.out.println(list.foldr(new IBinaryOp1<Integer, Integer>() {
public Integer apply(Integer a, Integer b) {
return a + b;
}
}, 0));
// foldr : リストのコピー
System.out.println(list.foldr(
new IBinaryOp1<Integer, IList>() {
public IList apply(Integer a, IList b) {
return b.cons(a);
}
},
new Nil()));
// foldl : 要素を足し合わせる
System.out.println(list.foldl(
new IBinaryOp2<Integer, Integer>() {
public Integer apply(Integer a, Integer b) {
return a + b;
}
},
0));
// foldl : 要素を掛け合せる
System.out.println(list.foldl(
new IBinaryOp2<Integer, Integer>() {
public Integer apply(Integer a, Integer b) {
return a * b;
}
},
1));
// メソッドチェーン : 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;
}
}).foldr(new IBinaryOp1<Integer, Integer>() {
public Integer apply(Integer a, Integer b) {
return a * b;
}
}, 1));
}
}
/**
* 空リスト
*/
public class Nil<A> implements IList<A> {
public IList<A> cons(A a) {
return new Cons(a, this);
}
public int length() {
return 0;
}
public int length(int acc) {
return acc;
}
@Override
public String toString() {
return "";
}
public <B> IList<B> map(IUnaryOp<A, B> f) {
return new Nil<B>();
}
public IList<A> filter(IPredicate<A> p) {
return new Nil<A>();
}
public <B> B foldr(IBinaryOp1<A, B> f, B z) {
return z;
}
public <B> B foldl(IBinaryOp2<B, A> f, B z) {
return z;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment