FizzBuzz ループ→再帰→Composite→Strategy→Visitor

最近FizzBuzzをblogで書くといいよみたいな流れになっている(曲解)ので

FizzBuzz - 文殊堂

id:monjudoh が言ったからというわけではないのだけど、FizzBuzzアルゴリズムの書き換えの話をしよう。

 やや昔のエントリになるけどもJavaFizzBuzz再帰で作ったというエントリをみつけた。

public class FizzBazzSaiki{
	public static void main(String[] args){
		System.out.println(func(args.length>0?Integer.parseInt(args[0]):30));
	}
	
	public static String func(int i){
		if(i == 1) return "1";
		System.out.println(func(i-1));
		return i%3==0? i%5==0? "FizzBazz"
		                     : "Fizz"
		             : i%5==0? "Bazz"
		                     : String.valueOf(i);
	}
}

んー!我ながら変態だ!

FizzBazzを作ったよ! - そうだ?Blogを書こう?

 Java的にはループをこのような再帰に展開するのは変態的なのだけど、関数型言語ではループカウンタを用いたループということはしなくて再帰で書くのが一般的。この再帰による書き換えでは変数への破壊的な代入がなくなるので、副作用をなくすことができる。プログラミング用語としての「副作用」については副作用 (プログラム) - Wikipediaを参照。

 今後の関数型言語の流行の兆しを見るに、こうしたループ→再帰への書き換え問題はすらすら答えれるように訓練しておくと後々役に立つと思われる。とはいえ、再帰への書き換えはJava屋には使えるポイントの少ない書き換えなので、ここからデザインパターンを利用した書き換えを行ってみよう。GoFデザインパターンのCompositeパターンにしてみる。

public class CompositeFizzBuzz {
	static abstract class Node {
		Node child;
		public abstract void fizzbuzz(int depth);
		public Node setChild(Node child) {
			this.child = child;
			return child;
		}
	}
	static class Number extends Node {
		public void fizzbuzz(int depth) {
			System.out.println(depth);
			this.child.fizzbuzz(depth + 1);
		}
	}
	static class Fizz extends Node {
		public void fizzbuzz(int depth) {
			System.out.println("Fizz");
			this.child.fizzbuzz(depth + 1);
		}
	}
	static class Buzz extends Node {
		public void fizzbuzz(int depth) {
			System.out.println("Buzz");
			this.child.fizzbuzz(depth + 1);
		}
	}
	static class FizzBuzz extends Node {
		public void fizzbuzz(int depth) {
			System.out.println("FizzBuzz");
			this.child.fizzbuzz(depth + 1);
		}
	}

	public static void main(String[] args) {
		Node first = new Number(); // 1
		Node temp = first;
		temp = temp.setChild(new Number()); //2
		temp = temp.setChild(new Fizz()); //3
		temp = temp.setChild(new Number()); //4
		temp = temp.setChild(new Buzz()); //5
		temp = temp.setChild(new Fizz()); //6
		temp = temp.setChild(new Number()); //7
		temp = temp.setChild(new Number()); //8
		temp = temp.setChild(new Fizz()); //9
		temp = temp.setChild(new Buzz()); //10
		temp = temp.setChild(new Number()); //11
		temp = temp.setChild(new Fizz()); //12
		temp = temp.setChild(new Number()); //13
		temp = temp.setChild(new Number()); //14
		temp = temp.setChild(new FizzBuzz()); //15
		temp = temp.setChild(first);

		first.fizzbuzz(1);
	}
}

 再帰の場合、条件分岐でFizzとBuzzを呼び分ける必要があった。Compositeパターンを利用する場合、分岐はポリモフィズムで行われるため、コード中に条件式は出てこない。代わりに15個のオブジェクトからなる環状単方向リストというデータ構造が必要となる。

 教科書的なCompositeパターンの説明では木構造を辿るが、今回は枝の分岐がいらないので単方向リストとなっている。単方向リストというデータ構造が木構造の特殊ケースであることを考えればこれもまたCompositeパターンであることが分かることだろう。

 データ構造を生成する部分で手抜きをしているため副作用を残しているが、FizzBuzz処理自体は副作用を持たない点に注目してもらいたい。

 さて、Compositeパターンの弱点として、木を構成する各種クラスに処理が分散し、かつ、それぞれのクラスにハードコーディングされる点が挙げられる。例えばFizz、Buzzの代わりにHoge、Piyoを出力せよ、と言われると既存のコードの修正となってしまう。それもあちこちのクラスの修正だ。

 既存コードの修正ではなく、新たなクラスを実装して追加することで機能変更できることが拡張性の点では好ましい。とすれば、GoFデザインパターンのStrategyパターンだ。

public class StrategyFizzBuzz {
	static interface Strategy {
		void doFizzBUzz(int depth);
	}
	static class HogePiyoStrategy implements Strategy{
		public void doFizzBuzz(int depth) {
			if (depth % 15 == 0) {
				System.out.println("HogePiyo");
				return;
			}
			if (depth % 3 == 0) {
				System.out.println("Hoge");
				return;
			}
			if (depth % 5 == 0) {
				System.out.println("Piyo");
				return;
			}
			System.out.println(depth);
		}
	}
	static class Node {
		Node child;
		public void fizzbuzz(Strategy strategy, int depth) {
			strategy.doFizzBuzz(depth);
			this.child.fizzbuzz(strategy, depth + 1);
		}
		public Node setChild(Node child) {
			this.child = child;
			return child;
		}
	}
	static class Number extends Node {
	}
	static class Fizz extends Node {
	}
	static class Buzz extends Node {
	}
	static class FizzBuzz extends Node {
	}

	public static void main(String[] args) {
		Node first = new Number(); // 1
		Node temp = first;
		temp = temp.setChild(new Number()); //2
		temp = temp.setChild(new Fizz()); //3
		temp = temp.setChild(new Number()); //4
		temp = temp.setChild(new Buzz()); //5
		temp = temp.setChild(new Fizz()); //6
		temp = temp.setChild(new Number()); //7
		temp = temp.setChild(new Number()); //8
		temp = temp.setChild(new Fizz()); //9
		temp = temp.setChild(new Buzz()); //10
		temp = temp.setChild(new Number()); //11
		temp = temp.setChild(new Fizz()); //12
		temp = temp.setChild(new Number()); //13
		temp = temp.setChild(new Number()); //14
		temp = temp.setChild(new FizzBuzz()); //15
		temp = temp.setChild(first);


		first.fizzbuzz(new HogePiyoStrategy(), 1);
	}
}

 StrategyオブジェクトへFizzBuzz処理を委譲するようにしたので、Strategy実装クラスを作成することで既存クラスに手を入れずに出力文字列を変えれるようになった。しかし、FizzBuzzを表現していた木構造はなんらの役も果たさなくなっている。StrategyのdoFizzBuzz()は副作用はないものの、ポリモフィズムに押し込んでいたはずの条件分岐がif文になって再び姿を現した。

 そこで、今度はdoFizzBuzz()にNodeの実装型を渡すようにしてif文による条件分岐をオーバーロードによる分岐にしてしまう。

public class VisitorFizzBuzz {
	static interface Visitor {
		void doFizzBUzz(Number node, int depth);
		void doFizzBUzz(Fizz node, int depth);
		void doFizzBUzz(Buzz node, int depth);
		void doFizzBUzz(FizzBuzz node, int depth);
	}
	static class HogePiyoVisitor implements Visitor{
		public void doFizzBUzz(Number node, int depth) {
			System.out.println(depth);
			node.child.fizzbuzz(this, depth + 1);
		}
		public void doFizzBUzz(Fizz node, int depth) {
			System.out.println("Hoge");
			node.child.fizzbuzz(this, depth + 1);
		}
		public void doFizzBUzz(Buzz node, int depth) {
			System.out.println("Piyo");
			node.child.fizzbuzz(this, depth + 1);
		}
		public void doFizzBUzz(FizzBuzz node, int depth) {
			System.out.println("HogePiyo");
			node.child.fizzbuzz(this, depth + 1);
		}
	}
	static abstract class Node {
		Node child;
		public abstract void fizzbuzz(Visitor visitor, int depth);
		public Node setChild(Node child) {
			this.child = child;
			return child;
		}
	}
	static class Number extends Node {
		public void fizzbuzz(Visitor visitor, int depth) {
			visitor.doFizzBUzz(this, depth);
		}
	}
	static class Fizz extends Node {
		public void fizzbuzz(Visitor visitor, int depth) {
			visitor.doFizzBUzz(this, depth);
		}
	}
	static class Buzz extends Node {
		public void fizzbuzz(Visitor visitor, int depth) {
			visitor.doFizzBUzz(this, depth);
		}
	}
	static class FizzBuzz extends Node {
		public void fizzbuzz(Visitor visitor, int depth) {
			visitor.doFizzBUzz(this, depth);
		}
	}

	public static void main(String[] args) {
		Node first = new Number(); // 1
		Node temp = first;
		temp = temp.setChild(new Number()); //2
		temp = temp.setChild(new Fizz()); //3
		temp = temp.setChild(new Number()); //4
		temp = temp.setChild(new Buzz()); //5
		temp = temp.setChild(new Fizz()); //6
		temp = temp.setChild(new Number()); //7
		temp = temp.setChild(new Number()); //8
		temp = temp.setChild(new Fizz()); //9
		temp = temp.setChild(new Buzz()); //10
		temp = temp.setChild(new Number()); //11
		temp = temp.setChild(new Fizz()); //12
		temp = temp.setChild(new Number()); //13
		temp = temp.setChild(new Number()); //14
		temp = temp.setChild(new FizzBuzz()); //15
		temp = temp.setChild(first);


		first.fizzbuzz(new HogePiyoVisitor(), 1);
	}
}

 こうすることで出来あがるのがGof Visitorパターンを用いたFizzBuzzだ。

 プログラミング能力を鍛えるためにも、こうした書き換えが自在にできるように訓練しておくといい。