Javaで関数型言語のreduceを実装してみる

始めに

目的

Javaで自前reduceを実装することで、関数型言語の考え方（特に再帰）に慣れるためです

実装方針や考え方

• ループを使わずに再帰を使って繰り返し処理を実装する。
• 特定の型に特化するのではなく、汎用的な型を扱えるようにする。
• ここでは、Java8で登場する機能はあえて使っていません。

工夫した点

インナークラス

ジェネリック型を使って、汎用的な型を扱えるようにしています。
例えば、配列の要素を足し上げる処理は数値型だけではなく、文字列型に対しても処理できるように字実装しています

Reduceクラスのreduceメソッド

再帰処理で使うデータ構造について

関数型言語で再帰を語る時によく出てくる
”集合Aの繰り返し処理を、一番目の要素とそれ以外の要素に分け、一番目の要素を処理した後に残りの要素を再帰処理をする関数の引数に渡して実装する”
点をJavaのStack(Deque)を使って実装しています。
ちなみに、最初の実装ではlistに対してget→removeの処理を行っていましたが、見た目にも美しくないし、結局やりたいことがFirst-In,First-Outだということに気が付いたので、Stackを使う実装に変更しました。

再帰処理のロジックについて

初回の再帰処理は引数で渡された要素が2つ以上場合、呼び出す関数の二つの引数に対してそれぞれ2回スタックをpopしてあげる必要があります。
このとき、再帰処理が初回かそうでないかはインスタンス変数のT _tがnullかどうかで判定しています

収穫点

• 再帰のロジックになれたかもしれない
  -ついでにJavaの総称型の使い方になれたかもしれない

FuncTest.java

	static public class Reduce<T>{
		private T _t ;
		public T reduce(Collection<T> b,Function<T> f){
			Deque<T> a = new ArrayDeque<T>(b);
			//スタックの要素がなくなったら再帰処理を終了する
			if(a.isEmpty()){
				return _t;
			}
			//要素数2以上のリストが渡された場合
			if(a.size() > 1){
				//最初に再帰処理が呼び出された時の処理
				if(_t==null){
					//リストの一番目と2番目を引数にセットする
					_t = f.aply(a.pop(),a.pop());
				}else{
					//2回目以降に再帰処理が呼び出された場合はインスタンス変数で保持した
					//値とスタックの先頭を引数で渡されたインナークラスのメソッドに渡す
					_t = f.aply(_t,a.pop());
				}
			//要素数1のリストが渡された場合
			}else{
				//最初に再帰処理が呼び出された時の処理
				if(_t==null)return a.pop();
				else{ 
					_t = f.aply(_t,a.pop());
     			}
			}
			return reduce(a,f) ;
		}
	}
	//Functionクラスのインターフェイス　abstractクラスで定義する
	static  abstract class Function<T>{
		public abstract T aply(T a, T b);
	}
	//配列の中身をすべて足し算します
	static class  FunctionAsAdd<T> extends Function<Integer>{
		public Integer aply(Integer a, Integer b){return a+b;};
	}
	//配列の中身をすべて掛け算します
	static class FunctionAsMultiplication<T> extends Function<Integer>{
		public Integer aply(Integer a, Integer b){return a*b;};
	}
	//配列の文字列をすべて連結します
	static class FunctionAsString<T> extends Function<String>{
		public String aply(String a, String b){return a+b;};
	}
	
	
	public static void main(String args[]){
		List<Integer>list = new ArrayList<Integer>();
		Collections.addAll(list, 1,2,3,4,5,6,7,8,9,10);
		System.out.println(
				(new Reduce<Integer>())
				.reduce(list,new FunctionAsAdd<Integer>())
				);//55が表示される
		System.out.println((new Reduce<Integer>())
				.reduce(list,new FunctionAsMultiplication<Integer>())
				);//3628800が表示される
		List<String> stringList= Arrays.asList( 
				new String[]{"1","2","3","4","5","6","7","8","9"});
		System.out.println((new Reduce<String>())
				.reduce(stringList,new FunctionAsString<String>())
				);//123456789が表示される
	}
}