Untitled



# RLE圧縮をトップダウンで実装する（Java）

「関数プログラミング実践入門」6章の例題をJava実装する


## らしからぬ Java 実装

RLE.compress("AAAABBBCC") とすると、戻り値 "A4B3C2" を返却するというテストを用意

```Java
//テスト
@Test
public void test() throws Exception {
	//期待する振る舞い
    assertThat(RLE.compress("AAAABBBCC"), is("A4B3C2"));
}

//RLE実装
public static class RLE {
	//エントリポイント
    public static String compress(final String str) {
        return null;
    }
}
```

compress を toCharAndRunLength関数と fromCharAndRunLength関数に分割するトップダウン・アプローチ

```Java
public static class RLE {
    //エントリポイント
    public static String compress(final String str) {
    	//関数合成
        final Function<String, String> executor =
        	toCharAndRunLength.andThen(fromCharAndRunLength);
        return executor.apply(str);
    }

    // "AAAABBBCC" -> [("A",4),("B",3),("C",2)] する関数
    private static final Function<String, List<Tuple<String, Integer>>> toCharAndRunLength =
    	str -> null;

    // [("A",4),("B",3),("C",2)] -> "A4B3C2" する関数
    private static final Function<List<Tuple<String, Integer>>, String> fromCharAndRunLength =
    	list -> null;
}
```

## fromCharAndRunLength関数の実装

fromCharAndRunLength関数 を rls2strs関数と cat関数に更に分割する

```Java
// [("A",4),("B",3),("C",2)] -> ["A4","B3","C2"] する関数
private static final Function<List<Tuple<String, Integer>>, List<String>> rls2strs =
	list -> null;

// ["A4","B3","C2"] -> "A4B3C2" する関数
private static final Function<List<String>, String> cat =
	list -> null;

// [("A",4),("B",3),("C",2)] -> "A4B3C2" する関数
private static final Function<List<Tuple<String, Integer>>, String> fromCharAndRunLength =
	list -> rls2strs.andThen(cat).apply(list);
```

cat関数を実装する

```Java
// ["A4","B3","C2"] -> "A4B3C2" する関数
private static final Function<List<String>, String> cat =
	list -> list.stream()
    			.collect(Collectors.joining());
```

rls2strs関数を実装する

```Java
// [("A",4),("B",3),("C",2)] -> ["A4","B3","C2"] する関数
private static final Function<List<Tuple<String, Integer>>, List<String>> rls2strs =
	list -> list.stream()
    			.map(tuple -> String.format("%s%s",
                							tuple._1,
                                            tuple._2.toString()))
    			.collect(Collectors.toList());
```


## toCharAndRunLength関数の実装

toCharAndRunLength関数を toRLs関数と toPairs関数に分割する

```Java
// "AAAABBBCC" -> ["AAAA","BBB","CC"] する関数
private static final Function<String, List<String>> toRLs =
	str -> null;

// ["AAAA","BBB","CC"] -> [("A",4),("B",3),("C",2)] する関数
private static final Function<List<String>, List<Tuple<String, Integer>>> toPairs =
	list -> null;

// "AAAABBBCC" -> [("A",4),("B",3),("C",2)] する関数
private static final Function<String, List<Tuple<String, Integer>>> toCharAndRunLength =
	str -> toRLs.andThen(toPairs).apply(str);
```

toPairs関数を実装する

```Java
// ["AAAA","BBB","CC"] -> [("A",4),("B",3),("C",2)] する関数
private static final Function<List<String>, List<Tuple<String, Integer>>> toPairs =
	list -> list.stream()
                .map(str -> new Tuple<String, Integer>(str.substring(0, 1), str.length()))
                .collect(Collectors.toList());
```

toRLs関数を実装する。Haskell であれば、標準ライブラリの group 関数で済むところが。。

```Java
// "AAAABBBCC" -> ["AAAA","BBB","CC"] する関数
private static final Function<String, List<String>> toRLs = str -> {
	//同じ文字が出現する間、この関数外変数に値を保持する
    final String[] stack = {""};
    final Function<String, List<String>> executor = strings -> {
        //文字列を一文字ずつに分割する
        final String[] chars = strings.split("");
        final List<String> collect = Stream.of(chars).map(chr -> {
            //スタックが空なら
            if (isEmpty(stack[0])) {
                stack[0] = chr;
                return null;
            }
            //スタック保持文字と同じなら
            if (stack[0].startsWith(chr)) {
                stack[0] = stack[0] + chr;
                return null;
            }
            //スタック保持文字と異なるなら
            final String result = Stream.of(stack).collect(Collectors.joining());
            stack[0] = chr;
            return result;
        }).collect(Collectors.toList());
        //スタック保持文字列を追加
        collect.add(stack[0]);
        //Null除外して返却
        return collect.stream()
        			  .filter(Objects::nonNull)
                      .collect(Collectors.toList());
    };
    return executor.apply(str);
};
```

## インラインに展開

すべて実装したので、toCharAndRunLength関数と fromCharAndRunLength関数をインライン化する

```Java
public static String compress(final String str) {
    final Function<String, String> executor = toRLs.andThen(toPairs)
                                                   .andThen(rls2strs)
                                                   .andThen(cat);
    return executor.apply(str);
}
```

テストが正しく動作することを確認する

```Java
//テスト
@Test
public void test() throws Exception {
    //期待する振る舞い
    assertThat(RLE.compress("AAAABBBCC"), is("A4B3C2"));
    assertThat(RLE.compress("AABCCCDDD"), is("A2B1C3D3"));
}

//RLE実装
public static class RLE {
    //エントリポイント
    public static String compress(final String str) {
        final Function<String, String> executor = toRLs.andThen(toPairs)
                                                       .andThen(rls2strs)
                                                       .andThen(cat);
        return executor.apply(str);
    }

    // "AAAABBBCC" -> ["AAAA","BBB","CC"] する関数
    private static final Function<String, List<String>> toRLs = str -> {
        final String[] stack = {""};
        final Function<String, List<String>> executor = strings -> {
            //文字列を一文字ずつに分割する
            final String[] chars = strings.split("");
            final List<String> collect = Stream.of(chars).map(chr -> {
                //スタックが空なら
                if (isEmpty(stack[0])) {
                    stack[0] = chr;
                    return null;
                }
                //スタック保持文字と同じなら
                if (stack[0].startsWith(chr)) {
                    stack[0] = stack[0] + chr;
                    return null;
                }
                //スタック保持文字と異なるなら
                final String result = Stream.of(stack).collect(Collectors.joining());
                stack[0] = chr;
                return result;
            }).collect(Collectors.toList());
            //スタック保持文字列を追加
            collect.add(stack[0]);
            //Null除外
            return collect.stream().filter(Objects::nonNull).collect(Collectors.toList());
        };
        return executor.apply(str);
    };

    // ["AAAA","BBB","CC"] -> [("A",4),("B",3),("C",2)] する関数
    private static final Function<List<String>, List<Tuple<String, Integer>>> toPairs =
    	list -> list.stream()
    		        .map(str -> new Tuple<String, Integer>(str.substring(0, 1), str.length()))
                                                                 .collect(Collectors.toList());

    // [("A",4),("B",3),("C",2)] -> ["A4","B3","C2"] する関数
    private static final Function<List<Tuple<String, Integer>>, List<String>> rls2strs =
    	list -> list.stream()
    		        .map(tuple -> String.format("%s%s", tuple._1, tuple._2.toString()))
                    .collect(Collectors.toList());

    // ["A4","B3","C2"] -> "A4B3C2" する関数
    private static final Function<List<String>, String> cat =
    	list -> list.stream()
        			.collect(Collectors.joining());
}
```

## その他

Java8の場合、stream() と collect() を書くのが手間なので、Streamで渡した方がコード量が削減できる。

```Java
// Stream["AAAA","BBB","CC"] -> Stream[("A",4),("B",3),("C",2)] する関数
private static final Function<Stream<String>, Stream<Tuple<String, Integer>>> toPairs =
	stream -> stream.map(str -> new Tuple<String, Integer>(str.substring(0, 1), str.length()));

// Stream[("A",4),("B",3),("C",2)] -> Stream["A4","B3","C2"] する関数
private static final Function<Stream<Tuple<String, Integer>>, Stream<String>> rls2strs =
	stream -> stream.map(tuple -> String.format("%s%s", tuple._1, tuple._2.toString()));

// Stream["A4","B3","C2"] -> "A4B3C2" する関数
private static final Function<Stream<String>, String> cat =
	stream -> stream.collect(Collectors.joining());
```

またすべて関数合成してから apply() するよりも、早めにstream化した方が、map() や collect() をインラインで記述できるため、Java8的には書きやすい。

```Java
public static class RLE {
    //エントリポイント
    public static String compress(final String str) {
        return toRLs.apply(str)
        			.map(toPairs)
                    .map(rls2strs)
                    .collect(Collectors.joining());
    }

    // "AAAABBBCC" -> Stream["AAAA","BBB","CC"] する関数
    private static final Function<String, Stream<String>> toRLs = str -> {
    	//省略
        return executor.apply(str).stream();
    };

    // ["AAAA","BBB","CC"] -> [("A",4),("B",3),("C",2)] する関数
    private static final Function<String, Tuple<String, Integer>> toPairs =
            str -> new Tuple<String, Integer>(str.substring(0, 1), str.length());

    // [("A",4),("B",3),("C",2)] -> ["A4","B3","C2"] する関数
    private static final Function<Tuple<String, Integer>, String> rls2strs =
            tuple -> String.format("%s%s", tuple._1, tuple._2.toString());
}
```

mapは複数回処理せずに、合成した関数を一度で処理する

```Java
public static class RLE {
        return toRLs.apply(str)
        			.map(toPairs.andThen(rls2strs))
                    .collect(Collectors.joining());
}
```