絵で理解するリスト処理 - java8 stream / javaslang - のおまけ

絵で理解するリスト処理 - java8 stream / javaslang - のおまけ記事！

いつも通り長すぎたので分離した。

ざっと行くぜ！

[おまけ - java8 stream]: 他の reduce

reduceの定義は java8 stream には３つあるけど、

他の２つを紹介する。

１つめはこれ。

Optional<T> reduce(BinaryOperator<T> accumulator);

Optional<T> reduce(     ((T, T) -> T) f);            // 簡略化
         T  reduce(T t, ((T, T) -> T) f);            // 最初の reduce の再掲

さっきと違うのはT tがないのと、戻りがOptionalに包まっている点。

どうしてかそうなるのかは、絵を見ればわかる。

最初のT tがある方

T tがない方

初期値を自分で指定するか、最初の一つを初期値とするかの違いが、T tの有無の違い。

で、どうして戻りがOptionalになってしまうかは、空リストの場合を考えるとわかる。

リストが空ならT tを最終結果にできる

T tがなくリストも空だとどうにもならない

初期値がなくて空リストだと、戻りが用意できないからだ。

[おまけ - java8 stream]: さらに他の reduce

残りの１つを紹介する。

２つめはこれ。

<U> U reduce(U identity, BiFunction<U, ? super T, U> accumulator, BinaryOperator<U> combiner);

U reduce(U u, ((U, T) -> U) f, ((U, U) -> U) g);    // 簡略化

U reduce(U u, ((U, T) -> U) f);                     // とりあえず、３つめの引数を忘れる
T reduce(T t, ((T, T) -> T) f);                     // 最初の reduce の再掲

謎の３つめの引数を忘れれば、最初のreduceとよく似ている。

これは「初期値がリストの型と違っていても畳み込めるよ」という意味であり、他の言語だとまず大体はこの形が標準だ。

で、最後の３引数めだが、java8 stream は並列実行を考慮しているので分割実行した結果をマージする方法を要求してくる。正直これは隠蔽して欲しい。

（内部処理ちゃんと読んでないので、これは本当に「イメージ」）

３引数のは少し抵抗があるかもしれないが、３引数めをノイズだと思えば他の言語と同じなので、避けずに習得しておくと色々と吉。

[おまけ - java8 stream]: reduce の応用

[10, 30, 45, 15]の総和が知りたいならsum使えば良いじゃん、って考えるのはその通り。

reduceは初期値の型が違う場合にこそ価値がある。初期値に違う型が使えれば、実質なんだってできるぞ。

例えば、(と)の羅列が正しく閉じ合っているかをチェックする、なんて処理もreduceでさっと書ける。

resolve(asList('(', '(', ')', ')'))   // true

resolve(asList('(', '(', ')'))        // false

resolve(asList('(', ')', ')', '('))   // false

private static boolean resolve(List<Character> cs) {
    return cs.stream()
            .reduce(
                    Optional.of(0),
                    (acc, c) -> c == '('
                            ? acc.map(n -> n + 1)
                            : acc.map(n -> n - 1).filter(n -> n >= 0),
                    (acc1, acc2) -> acc1
                            .flatMap(v1 -> acc2.map(v2 -> v1 + v2))
            ).equals(Optional.of(0));
}

初期値をOptional(0)にして、畳み込みながら(ならOptional(n)に.map(n + 1)を、)ならOptional(n)に.map(n - 1)にする。ただしOptional(0)を下回ったらemptyとする。
一度emptyになってしまえば、empty.map(n + 1)をしても二度とOptional(0)に戻ることはない。

畳み終わって最後にOptional(0)であれば、(と)の数は一緒だし、一度も過分に)がなかったってことだ。

２つのOptionalをマージする３引数めは、両方Optional(n)であれば中見で加算すれば良い。両方〜〜なら、ってのはflatMapだ。これがすぐ出てくると良い感じ。

U reduce(U u, ((U, T) -> U) f, ((U, U) -> U) g);    // 再掲

型とにらめっこしつつ、習得しよう。

[おまけ - java8 stream]: reduce の初期値の使われるタイミング

reduce は計算の順番や向きに気をつけないといけないので、さらっと例を載せる。

この２つは同じ結果になる。

Stream.of(1, 2, 3).reduce((acc, n) -> acc + n).orElse(0)    // 6
Stream.of(1, 2, 3).reduce(0, (acc, n) -> acc + n)           // 6

けど、この２つの結果は違う。

Stream.of("1", "ok", "15:10").reduce((acc, s) -> acc + " | " + s).orElse("")    // 1 | ok | 15:10
Stream.of("1", "ok", "15:10").reduce("", (acc, s) -> acc + " | " + s)           //  | 1 | ok | 15:10

自分で絵を描いてみると違いが理解できるはず。

覚えておくと吉。

[おまけ - javaslang]: reduce の方向

せっかくreduceに触れたので、ついでに少しだけ javaslang のreduceを見ておこう。

List.of("1", "ok", "15:10").reduceRightOption((s, acc) -> acc + " | " + s).getOrElse("");    // 15:10 | ok | 1

右から畳み込むreduceも、言語やライブラリによってはまぁまぁ用意されている。（これは(acc, s) -> ではなくて(s, acc) -> なので注意）

もちろんこれを使う場合も、左からの場合と結果が変わることが多いので、注意する。

reduceはこれでおしまい！

[おまけ - javaslang]: takeWhile

リスト操作で覚えておくと便利なtakeWhileを紹介する。こいつも javaslang を使って紹介する。
（まさか java8 stream にtakeWhileがないとは知らなかった...）

最初のお題のラベル:millisecの行を、早い順にして 30 未満のところだけにしてみよう。

lines
    .filter(line -> line.contains(":"))
    .map(line -> Integer.valueOf(line.split(":")[1]))
    .sorted()
    .takeWhile(n -> n < 30);                           // [10, 15]

takeWhileは「先頭から特定の条件に合致する間だけ拾う」って感じだ。
dropWhileと合わせて案外よく使うので、これも覚えておくと吉。

[おまけ - javaslang]: zip

最後にもうひとつ、zipも案外よく使うので紹介する。こいつも javaslang を使って紹介する。

こいつは２つのリストの同じ箇所をペアリングする様なイメージだ。ジッパーみたいな感じって思うとわかりやすいかも。

List.of(1, 2, 3)
    .zip(List.of('a', 'b', 'c'))    // [(1, a), (2, b), (3, c)]

（`zip`は`Tuple`という違う型をペアリングできる型がないと使えない。）

AとBをペアリングしたい場合以外にも例えば、Integerのリストのそれぞれの隙間の大きさが知りたいときなんかは、同じリストを１つずらしてzipしてみる、なんてやり方がある。

List<Integer> times = List.of(10, 15, 35, 60); // これを [15 - 10, 35 - 15, 60 - 35] にしたい

times
    .zip(times.subSequence(1))
    .map(t -> t._2 - t._1);                    // [5, 20, 25]

先頭から順に処理するって考えるとreduce使う？って思うかもしれないけど、絵にすれば全然違う。
（reduceはお隣さんとの計算ではなくてそこまでの総和（とか）とひとつずつを計算しているから、隙間計算とかは素直にはできない。）

ログファイルなんかを上手くfilter and mapして、zipして１行毎の処理時間差分を取ってreverse sort and takeWhileなんてしてみると、500 ms 以上かかってる行を遅い順に表示する、なんてことができる。

[おまけ - java8 stream / javaslang]: map のメリット

「メリットがわからん」「for で良くね？」って話が絶対に出るけど、学習コストに見合うメリットは当然ある。

いくつかあるけど、軽く３つ挙げてみようと思う。

1. 状況とやりたいことを分離出来る

例えばString -> Integerのこんな function がある。

private static Integer toIntAndTwice(String s) {
    return Integer.valueOf(s) * 2;
}

この function を「複数のStringがある場合」、「最大１つのStringがある場合」、「フォーマット不正かもしれないStringがある場合」に適用するコードを愚直に書くと、こうなる。

Listの例

List<Integer> result = List.empty();

List<String> org = ...; // List.of(1, 2, 3) or empty

for (String x : org) {
    result.append(toIntAndTwice(x));
}

return result;

Optionの例

Option<Integer> result;

Option<String> org = ...; // Option.of(1) or empty

if (org.isEmpty()) {
    result = Option.none();
} else {
    result = Option.of(toIntAndTwice(org.get()));
}

return result;

tryの例

Integer result;

String org = ...; // "1" or "x"

try {
    result = toIntAndTwice(org);
} catch (Throwable t) {
    result = null;
}

return result;

toIntAndTwiceを特定の状況にあるStringに適用するのに、全然違うコードを書かないといけない。

これをmapで書いてみるとこうなる。

Listの例

List<String> org = ...;
List<Integer> mapped = org.map(JSMain::toIntAndTwice);
return mapped;

Optionの例

Option<String> org = ...;
Option<Integer> mapped = org.map(JSMain::toIntAndTwice);
return mapped;

Tryの例

Try<String> org = ...;
Try<Integer> mapped = org.map(JSMain::toIntAndTwice);
return mapped;

同じ見た目になるね！
これは「ListやOptionの持つ特定の状況におけるルール」と「実際にやりたいこと（toIntAndTwice）」が分離されていて、前者が言語にフォローしてもらえているからだ。

ついでに、ここまでコードが似てるともっと共通化出来る気がするね？
javaslang のListやOptionはValueを継承しているので、こんな事もできる。

こんなValue<T> -> Value<R>を定義しておけば、

private static Value<Integer> mapAnyType(Value<String> org) {
    return org.map(JSMain::toIntAndTwice);
}

引数がListでもOptionでも動く！

Listの例

Value<Integer> m1 = mapAnyType(List.of("1", "2", "3")); // List(2, 4, 6)

Optionの例

Value<Integer> m2 = mapAnyType(Option.none());          // None

Tryの例

Value<Integer> m3 = mapAnyType(Try.of(() -> "x"));      // Failure(java.lang.NumberFormatException: For input string: "x")

これなら同じコードで違う状況が捌けるので、例えば有料オプションの解約処理を用意しておいて、「一括で解約する機能（List）」、「持っているなら解約する機能（Option）」、「持っているはずなので解約する機能（Try）」が一気に実現できる。

この「状況」と「処理」の分離が一番のメリットだと思う。

2. 一時変数が登場しない

みんな大好きレガシーコード。こんなのよくあるよね。

// 初期化
result = 0;
flag = false;

for (i ...) {
    result = ...;

    // 〜〜が終わっているか
    if (i < ...) {
        result = ...;
        flag = true;
    }

    // 〜〜なら終了
    if (flag) {
        return result;
    }

    // 次に〜〜でループ
    for (j ...) {
        result = ...;

        // 〜〜なら終了
        if (j < ...) {
            return result;
        }
    }
    // 初期化
    flag = false;
}

// リターン
return result;

このコードにあるreturn result;はテキストとしては同じなのに中身は全く違うよね。（多分、ね。僕も知らん。）

行に前後関係があるのでその行だけコピペしたりできないし、コメントでブロックを作ってる風だけど、実質これは巨大な１ブロックでしかない。

これが例えばさっきのコードみたいになっていると、引数３つの全ての行が独立して機能するし、returnしてはいけない処理中の変数というのがメソッドスコープにない。
（;が１つなので、このコードは１行。なので隙間状態があり得ない。）

return cs.stream()
        .reduce(
                Optional.of(0),
                (acc, c) -> c == '(' ? acc.map(n -> n + 1) : acc.map(n -> n - 1).filter(n -> n >= 0),
                (acc1, acc2) -> acc1.flatMap(v1 -> acc2.map(v2 -> v1 + v2))
        ).equals(Optional.of(0));

こうなっている方が圧倒的に再利用性が高いし、品質も高いと思う。
（もちろん共有コードでやるならもう少し丁寧にした方が良いと思うけど。２引数めはちゃんと名前をつけて軽くテストコードも書く、３引数めはReduceUtil::mergeOptionalにする、とか。effective java 3 版もそんなことを言っていた気がする。）

3. 別の言語の（に）経験が活かせる

詳細は次で触れるが、考え方自体を知っていればよほど特殊な言語でもない限り初見でも割となんとかなる。

java8 stream を習得して ruby に行ってみればリスト操作はすぐできるだろうし、java8 初心者でも python 経験者なら stream はできるだろう。

[おまけ]: 単語帳

直前のメリットでも触れたが、大抵の言語ではmap, filter, reduceは用意されている。

知らない言語を仕事で急遽メンテしないといけない時とか、拾ったツールにちょっと手を入れたいときとかに、単語と処理イメージさえわかっていれば結構なんとかなる。
なので最後によく聞く言語で同様の処理をする方法をまとめて終わりにする。

（(*)が付いている箇所は、上手く使えば似たことが出来るよ、って感じ）

lang	map	filter	reduce(zero / left) reduce(head / left) reduce(zero / right) reduce(head / right)	take while	zip
java	map	filter	reduce reduce - -	-	-
groovy	collect	findAll	inject inject - -	takeWhile	transpose (*)
scala	map	filter	reduceLeft / reduceLeftOption foldLeft reduceRight / reduceRightOption foldRight	takeWhile	zip
python	map	filter	reduce - - -	itertools.takewhile	zip
php	array_map	array_filter	array_reduce array_reduce - -	-	array_map (*)
ruby	map / collect	select	reduce / inject reduce / inject - -	take_while	zip
js	map	filter	reduce reduce reduceRight reduceRight	-	-
haskell	map	filter	foldl foldl1 foldr foldr1	takeWhile	zip

map / collect, filter, reduce / fold / injectあたりの単語を覚えておけば、大抵の言語は何とかなるよ、ってこと。

map vs collectやreduce vs injectは、調べてみると面白いかも。

おわり

ここまで読んでくれた人がもしいたら、ありがとうございます。

宣言した日にちゃんと記事が間に合って良かった。おしまい。