文字列変換処理の合成

自社で共通で使ってる全角→半角の文字列変換のプログラムが遅いので中身を見てみた。
中身見てみると、以下のようにラテン文字の変換とカナの変換を合成していた。

    public static String zen2Han(final String p) {
        return kanaZen2Han(latinZen2Han(p));
    }

まあ考え方自体は悪くないと思う。というかむしろ好き。

で、それぞれの中を見ると、それぞれの中でループして、Stringを生成していた。

    public static String kanaZen2Han(final String p) {
        if (p == null) {
            return p;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0, j = 0; i < p.length(); i++) {
            ...
        }
        return sb.toString();
    }
    public static String latinZen2Han(final String p) {
        if (p == null) {
            return p;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < p.length(); i++) {
            ...
        }
        return sb.toString();
    }

途中の変換結果を一旦文字列で取り出してから、その直ぐ後にまたばらしてループするのはいかにも無駄そうだ。
処理を合成するというアイデアは生かしつつオーバーヘッドを減らしたい。

実装

全体の方針として、先頭で文字列を文字(というかCodePoint)にばらして逐次的に処理できるようにする。で、最後に一回だけCodePointの列をまとめて文字列に変換する。

まず、CodePointを逐次的に受け取って処理するインタフェースを定義

/** CodePointを逐次的に受け取って処理するインタフェース */
public interface SequenceProcessor {
    void process(int codePoint);
}

CodePointを逐次的に生成してSequenceProcessorに渡すインタフェースを考える。

/** CodePointを逐次的に生成するインタフェース */
public interface SequenceGenerator {
    /**
     * CodePointを逐次的に生成し、processorに渡して処理する。
     */
    void run(SequenceProcessor processor);
}

文字列の保持、というかSequenceGeneratorを保持するクラスを定義する。

/** 文字列のシーケンスをあらわすクラス 。 */
public class StringSequence {
    /** CodePointを生成する能力 */
    private SequenceGenerator generator;
    private StringSequence(SequenceGenerator generator) {
        this.generator = generator;
    }
    // processorを渡して実際に処理を行う。
    public void run(SequenceProcessor processor) {
        generator.run(processor);
    }
    // SequenceGeneratorを元にStringSequenceを生成する。
    public static StringSequence of(final SequenceGenerator generator) {
        return new StringSequence(generator);
    }
    // 文字列を元にStringSequenceを生成する。
    public static StringSequence of(final String source) {
        return of(new SequenceGenerator() {
            @Override
            public void run(SequenceProcessor processor) {
                for (int i = 0, c = source.length(); i < c; i = source.offsetByCodePoints(i, 1)) {
                    processor.process(source.codePointAt(i));
                }
            }
        });
    }
    // 文字列をStringとして取り出す。
    public String getString() {
        final StringBuilder sb = new StringBuilder();
        run(new SequenceProcessor() {
            @Override
            public void process(int codePoint) {
                sb.appendCodePoint(codePoint);
            }
        });
        return sb.toString();
    }
}

例えば文字列"abc"を大文字にして標準出力にプリントする処理は以下のようになる。

        // 一文字ずつ大文字にして出力するSequenceProcessor。
        SequenceProcessor printEachUc = new SequenceProcessor() {
            @Override
            public void process(int codePoint) {
                int upperCase = Character.toUpperCase(codePoint);
                System.out.print(Character.toChars(upperCase));
            }
        };

        String source = "abc";
        StringSequence seq = StringSequence.of(source);
        seq.run(printEachUc);

変換の合成

文字の変換を行うインタフェースを定義し、合成を行えるようにする。

/** 文字の変換を行うインタフェース */
public interface StringConverter {
    StringSequence convert(final SequenceGenerator generator);
}

StringConverterはSequenceGeneratorを受け取り、StringSequenceを生成する。
このままでは使いにくいので一文字分の変換処理を行う部分だけを切り出した抽象スーパークラスを定義しておく。

/** 変換メソッドだけを切り出したStringConverterの抽象スーパークラス */
public abstract class AbstractStringConverter implements StringConverter {
    public final StringSequence convert(final SequenceGenerator generator) {
        return StringSequence.of(new SequenceGenerator() {
            public void run(final SequenceProcessor processor) {
                generator.run(new SequenceProcessor() {
                    public void process(int codePoint) {
                        AbstractStringConverter.this.process(codePoint, processor);
                    }
                });
            }
        });
    }
    /**
     * 一文字分の変換処理を行う
     * @param codePoint 変換対象となる文字のCodePoint
     * @param processor 出力先
     */
    protected abstract void process(int codePoint, SequenceProcessor processor);
}

StringConverterを受け取ってStringSequenceを生成するメソッドをStringSequenceに定義する。

/** 文字列のシーケンスをあらわすクラス 。 */
public class StringSequence {
...
    public StringSequence composite(final StringConverter converter) {
        return converter.convert(generator);
    }
}

例えば、「文字列を大文字化する処理」と「空白をスキップする処理」の合成は、以下のようになる。

        StringConverter toUpperCase = new AbstractStringConverter() {
            @Override
            protected void process(int codePoint, SequenceProcessor processor) {
                processor.process(Character.toUpperCase(codePoint));
            }
        };
        StringConverter skipSpace = new AbstractStringConverter() {
            @Override
            protected void process(int codePoint, SequenceProcessor processor) {
                if (!Character.isSpaceChar(codePoint)) {
                    processor.process(codePoint);
                }
            }
        };
        String source = "Pine Apple";
	// 大文字にし、空白をスキップし、文字列化する。
        String result =
            StringSequence.of(source)
                .composite(toUpperCase)
                .composite(skipSpace)
                .getString();

        assertEquals("PINEAPPLE", result);

文字列変換モナド？

StringSequenceクラスは、of()がunit、composite()がbindと考えるとモナドのようなものになっている。(というかそういう風に書いた。)
但し特別なものという訳ではなくてただのListの亜種のようなものだ。

Genericに書き下すと下のような感じになる。(ConverterのシグネチャをSequenceGenerator→Sequence<S>じゃなくてT→Sequence<S>に変更している。)

import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import java.util.List;
import org.junit.Test;

public class Sequences {
    /** データを逐次的に受け取って処理するインタフェース */
    public interface SequenceProcessor<T> {
        void process(T element);
    }
    /** データを逐次的に生成するインタフェース */
    public interface SequenceGenerator<T> {
        void run(SequenceProcessor<T> processor);
    }
    /** データの変換をおこなうインタフェース */
    public interface Converter<T, S> {
        Sequence<S> convert(T element);
    }
    /** データを逐次的に生成する能力をラップして合成可能にしたもの */
    public static class Sequence<T> {
        private SequenceGenerator<T> generator;
        public Sequence(SequenceGenerator<T> run) {
            this.generator = run;
        }
        public void run(SequenceProcessor<T> processor) {
            generator.run(processor);
        }
        public static <T> Sequence<T> unit(final SequenceGenerator<T> generator) {
            return new Sequence<T>(generator);
        }
        public static <T> Sequence<T> unit(final T element) {
            return unit(new SequenceGenerator<T>() {
                public void run(SequenceProcessor<T> processor) {
                    processor.process(element);
                }
            });
        }
        public <S> Sequence<S> bind(final Converter<T, S> converter) {
            return unit(new SequenceGenerator<S>() {
                @Override
                public void run(final SequenceProcessor<S> processor) {
                    Sequence.this.run(new SequenceProcessor<T>() {
                        @Override
                        public void process(T element) {
                            converter.convert(element).run(processor);
                        }
                    });
                }
            });  
        }
        public static <S, T> Converter<Sequence<T>, S> ext(final Converter<T, S> converter) {
            return new Converter<Sequence<T>, S>() {
                @Override
                public Sequence<S> convert(Sequence<T> sequence) {
                    return sequence.bind(converter);
                }
            };
        }
        // flatten = bind(id) = bind(ext(unit))
        public static <T> Sequence<T> flatten(Sequence<Sequence<T>> ss) {
            Converter<T, T> unit = new Converter<T, T>() {
                public Sequence<T> convert(T element) {
                    return unit(element);
                }
            };
            return ss.bind(ext(unit));
        }
//        // Functionはguavaの定義を参照
//        // map(f, m) = bind(m, ( \x -> unit (f x) ))
//        public static <S, T> Sequence<S> map(final Function<T, S> f, Sequence<T> c) {
//            return c.bind(new Converter<T, S>() {
//                @Override
//                public Sequence<S> convert(T element) {
//                    return Sequence.<S>unit(f.apply(element));
//                }
//            });
//        }
    }
    public static <T> List<T> toList(Sequence<T> sequence) {
        final List<T> list = new ArrayList<T>();
        sequence.run(new SequenceProcessor<T>() {
            @Override
            public void process(T element) {
                list.add(element);
            }
        });
        return list;
    }
/*

テスツ

 */
    public static Sequence<Integer> fromString(final String source) {
        return Sequence.unit(new SequenceGenerator<Integer>() {
            @Override
            public void run(SequenceProcessor<Integer> processor) {
                for (int i = 0, c = source.length(); i < c; i = source.offsetByCodePoints(i, 1)) {
                    processor.process(source.codePointAt(i));
                }
            }
        });
    }
    public static Converter<Integer, Integer> unit() {
        return new Converter<Integer, Integer>() {
            @Override
            public Sequence<Integer> convert(Integer element) {
                return Sequence.unit(element);
            }
        };
    }
    private static Converter<Integer, Integer> toUpperCase = new Converter<Integer, Integer>() {
        @Override
        public Sequence<Integer> convert(final Integer data) {
            return new Sequence<Integer>(new SequenceGenerator<Integer>() {
                @Override
                public void run(SequenceProcessor<Integer> processor) {
                    processor.process(Character.toUpperCase(data));
                }
            });
        }
    };
    private static Converter<Integer, Integer> skipSpace = new Converter<Integer, Integer>() {
        @Override
        public Sequence<Integer> convert(final Integer codePoint) {
            return new Sequence<Integer>(new SequenceGenerator<Integer>() {
                @Override
                public void run(SequenceProcessor<Integer> processor) {
                    if (!Character.isSpaceChar(codePoint)) {
                        processor.process(codePoint);
                    }
                }
            });
        }
    };

    // 拡張スタイルのモナド則
    // (return x) >>= f ≡ f x
    @Test
    public void testRule1() {
        Converter<Integer, Integer> unit = unit();
        Converter<Integer, Integer> f = toUpper;
        Integer x = 65;

        assertEquals(
            toList(unit.convert(x).bind(f)),
            toList(f.convert(x))
        );
    }
    
    // m >>= return ≡ m
    @Test
    public void testRule2() {
        Converter<Integer, Integer> unit = unit();
        Sequence<Integer> m = fromString("abc");
        assertEquals(
            toList(m.bind(unit)),
            toList(m)
        );
    }

    // (m >>= f) >>= g ≡ m >>= ( \x -> (f x >>= g) )
    @Test
    public void testRule3() {
        final Converter<Integer, Integer> f = toUpperCase;
        final Converter<Integer, Integer> g = skipSpace;
        
        Sequence<Integer> m = fromString("pine apple");

        assertEquals(
                toList(m.bind(f).bind(g)),
 
                toList(m.bind(new Converter<Integer, Integer>() {
                    @Override
                    public Sequence<Integer> convert(Integer element) {
                            return f.convert(element).bind(g);
                        }
                    }
                ))
        );
    }
}

「データを逐次的に生成する能力」をラップして合成可能にしたもの、というイメージ。

これを文字列変換に使おうとすると一文字単位でIntegerとSequenceが生成されてとても遅くなるので直接は使えない。
Listの生成が低コストだったり文字列もListで表現されるような下地がないと難しいかも。

あとこの実装では、結果を取り出すのに副作用のある関数を使用しなければならないのが関数型言語的な観点でいうととても残念な感じ。まあそこまで頑張るのは止めた。
m文字→n文字の変換とかバッファリングのような、状態を持ちたい変換が出てきたら、本当はListに対してreduce or foldを使いつつListを生成するんだろうと思う。

関数型言語のListはよく出来てるなあと。