Skip to content

Instantly share code, notes, and snippets.

@asufana

asufana/RLE圧縮をトップダウンで実装する.md

Last active December 14, 2015 03:03
Show Gist options
  • Save asufana/16c4dd2258f918fbbd44 to your computer and use it in GitHub Desktop.
Save asufana/16c4dd2258f918fbbd44 to your computer and use it in GitHub Desktop.
Download ZIP
RLE圧縮をトップダウンで実装する（Java）
Raw
RLE圧縮をトップダウンで実装する.md

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

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

らしからぬ Java 実装

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

//テスト
@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関数に分割するトップダウン・アプローチ

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関数に更に分割する

// [("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関数を実装する

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

rls2strs関数を実装する

// [("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関数に分割する

// "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関数を実装する

// ["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 関数で済むところが。。

// "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関数をインライン化する

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

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

//テスト
@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で渡した方がコード量が削減できる。

// 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的には書きやすい。

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は複数回処理せずに、合成した関数を一度で処理する

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

Haskellライブラリ相当をJavaで用意する

toRLs関数を改善するために、Haskell標準ライブラリが持つ span関数、group関数相当を用意する

import static org.apache.commons.lang.StringUtils.*;
import java.util.*;
import lombok.experimental.*;
import play.libs.F.Tuple;

@ExtensionMethod(Haskell.class)
public class Haskell {
    
    public static XXS xxs(final String str) {
        return XXS.xxs(str);
    }
    
    //x:xs分解
    public static class XXS {
        private final Tuple<String, String> xxs;
        
        public static XXS xxs(final String str) {
            return new XXS(str);
        }
        
        public XXS(final String str) {
            if (isEmpty(str)) {
                xxs = new Tuple<>(null, null);
            }
            else {
                xxs = new Tuple<>(str.substring(0, 1), str.substring(1, str.length()));
            }
        }
        
        public String x() {
            return xxs._1;
        }
        
        public String xs() {
            return xxs._2;
        }
    }
    
    //  span                 :: (a -> Bool) -> [a] -> ([a],[a]) //評価関数とリストを引数に受けてtupleを返却する
    //  span _ xs@[]         =  (xs, xs) //リストが空なら終了
    //  span p xs@(x:xs')
    //           | p x       =  let (ys,zs) = span p xs' in (x:ys,zs) //評価関数がtrueの場合、spanを再帰で処理する
    //           | otherwise =  ([],xs) //評価関数がfalseの場合
    
    //まったく汎用的ではないspan関数実装
    // A, "AABBCCAA" -> ("AA","BBCCAA") する関数
    public static Tuple<String, String> span(final String key, final String value) {
        if (isEmpty(key)) {
            throw new IllegalArgumentException();
        }
        if (isEmpty(value)) {
            return new Tuple<>("", "");
        }
        if (key.equals(value.xxs().x())) {
            final Tuple<String, String> spaned = span(key, value.xxs().xs());
            return new Tuple<>(value.xxs().x() + spaned._1, spaned._2);
        }
        return new Tuple<>("", value);
    }
    
    //    group             :: Eq a => [a] -> [[a]]
    //    group             =  groupBy (==)
    //    groupBy           :: (a -> a -> Bool) -> [a] -> [[a]]
    //    groupBy _  []     =  []
    //    groupBy eq (x:xs) =  (x:ys) : groupBy eq zs
    //                         where (ys,zs) = span (eq x) xs
    
    //まったく汎用的ではないgroup関数実装
    // "AAAABBBCC" -> ["AAAA","BBB","CC"] する関数
    public static List<String> group(final String value) {
        if (isEmpty(value)) {
            return Collections.emptyList();
        }
        final Tuple<String, String> spaned = span(value.xxs().x(), value.xxs().xs());
        final List<String> list = new ArrayList<String>() {
            {
                add(value.xxs().x() + spaned._1);
                addAll(group(spaned._2));
            }
        };
        return list;
    }
}

これを利用するとシンプルに書ける

//テスト
@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) {
        return group(str)
                  .stream()
                  .map(toPairs.andThen(rls2strs))
                  .collect(Collectors.joining());
    }

    // ["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>, Sring> rls2strs =
    	tuple -> String.format("%s%s", tuple._1, tuple._2.toString());
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment