1. suzuki-hoge

    Posted

    suzuki-hoge
Changes in title
+絵で理解するリスト処理 - java8 stream / javaslang -
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,562 @@
+「java8 で stream やってみたけど慣れねー」とか「ちょっと難しいことしようとするとできねー」ってのを良く聞くのでまとめてみるよ。
+
+型さえ把握すれば8割方わかった様なもんなので、それを絵にしてみるよ。
+
+ちなみに、記事は長いけど最初の`[本編 -`って見出しの箇所まで読めば十分だ!
+
+## [本編 - java8 stream]: filter, map, reduce
+基本の3手を押さえよう。
+
+`reduce`には馴染みがないかもしれないけど、Google が提唱した`MapReduce`モデルってので`map`とは一緒に語られるよ。-> [wiki](https://ja.wikipedia.org/wiki/MapReduce)
+
+以下の例題を使って見て行くよ。
+
+```java
+/*
+ * 以下の様なログがある
+ * ラベル もしくは ラベル:millisec の形式で1行ずつ出力される
+ *
+ * millisec の総和を求めよ
+ */
+List<String> lines = Arrays.asList(
+ "application-boot", "access-dispatch:10", "dispatched", "authentication:30", "database-access:45", "response-creation:15", "access-logging"
+);
+```
+
+大事なのはとにかく型なので、Generics にビビらずにそこだけはしっかり確認していくよ。
+
+それから、こんな絵が大量に出てくるよ。
+
+<img width="720" alt="legend.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/c00daf83-a280-9567-b355-594b11dbc644.png">
+
+`A -> B f`って書いてあるのは java のコードにすると`B f(a);`ってことで、`A`や`B`には`String`や`Optional<Integer>`などの具体型が入ります。つまり Generics のことです。
+
+### filter
+`filter`の定義はこう。
+
+```java
+Stream<T> filter(Predicate<? super T> predicate);
+```
+
+`Predicate<T>`は「引数が`T`で戻り値が`bool`」ってこと、`? super T`とかは今は忘れておっけー。
+
+`Predicate<T>`の型表記を`T を bool にする`って捉えて、`(T -> bool)`って書いてみよう。
+ついでに Generics も簡略化してしまおう。
+
+```java
+Stream<T> filter((T -> bool) f);
+```
+
+`filter`を使って`lines`を`:`のある行だけにするのは、こう書ける。
+
+```java
+lines.stream()
+ .filter(line -> line.contains(":")) // ["access-dispatch:10", "authentication:30", "database-access:45", "response-creation:15"]
+```
+
+定義を`T -> bool`と書いてみると、実装の`line -> line.contains(":")`が同じ様に見える。
+(このお題では、`T`は具体的には`String`ってこと)
+
+絵に描くとこんな感じだろうか。
+
+<img width="720" alt="filter.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/7b829ea7-5bd3-43ce-69ae-3cd3cb400f47.png">
+
+`filter`は **型** は変わらなくて、**数** が変わる変換ってことだ。
+
+### map
+`map`の定義はこう。
+
+```java
+<R> Stream<R> map(Function<? super T, ? extends R> mapper);
+```
+
+こっちも同じ様に簡略化すると、こうだ。
+
+```java
+Stream<R> map((T -> R) f);
+```
+
+`map`を使って`ラベル:millisec`の行を`Integer`にするのは、`filter`の続きにこう書ける。
+
+```Java
+lines.stream()
+ .filter(line -> line.contains(":")) // ["access-dispatch:10", "authentication:30", "database-access:45", "response-creation:15"]
+ .map(line -> Integer.valueOf(line.split(":")[1])) // [10, 30, 45, 15]
+```
+
+ここも定義の`T -> R`と実装が同じ形をしている。
+(このお題では、`R`は具体的には`Integer`ってことだから、`T -> R`が`String -> Integer`に見えていると良い感じ)
+
+絵に描くとこんな感じだろうか。
+
+<img width="720" alt="map.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/67299e52-5a4d-d015-d534-5c9439d2a399.png">
+
+`map`は **数** は変わらなくて、 **型** が変わる変換ってことだ。
+
+### reduce
+`reduce`の定義は java8 stream には3つあるけど、今から使うのはこうだ。
+
+```java
+T reduce(T identity, BinaryOperator<T> accumulator);
+```
+
+`BinaryOperator<T>`は少し見慣れないけど、「引数が`T`を2つで戻り値も`T`」ってことだ。
+これもビビらずに簡略化してみよう。
+
+```java
+T reduce(T t, ((T, T) -> T) f);
+```
+
+`reduce`は一般に「畳み込み」と言われていて、リストの先頭から順に結果を蓄積していく処理だ。
+
+`reduce`を使って`Integer`の行を`Integer`の総和にするのは、`map`の続きにこう書ける。
+
+```java
+lines.stream()
+ .filter(line -> line.contains(":")) // ["access-dispatch:10", "authentication:30", "database-access:45", "response-creation:15"]
+ .map(line -> Integer.valueOf(line.split(":")[1])) // [10, 30, 45, 15]
+ .reduce(0, (acc, n) -> acc + n) // 100
+```
+
+定義に少し括弧が多いけど、`T, (T, T) -> T`と`0, (acc, n) -> ...`が同じ形をしているから少しはわかりやすいはず。
+
+絵に描くとこんな感じだろうか。
+
+<img width="720" alt="reduce with zero a.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/4267d77f-846e-c7f3-1185-f5b619cc675f.png">
+
+`reduce`は **リストの要素** が **単一の結果** になる処理だ。
+
+### まとめ
+これでクリアー!
+
+```
+ * millisec の総和を求めよ
+```
+
+
+
+```java
+// ( 再掲 )
+
+lines.stream()
+ .filter(line -> line.contains(":")) // ["access-dispatch:10", "authentication:30", "database-access:45", "response-creation:15"]
+ .map(line -> Integer.valueOf(line.split(":")[1])) // [10, 30, 45, 15]
+ .reduce(0, (acc, n) -> acc + n) // 100
+```
+
+で解けた。
+
+一応全体の絵を載せておく。
+
+<img width="720" alt="resolve.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/5fd36f90-16f7-e2b0-d9ed-c8edf074a17c.png">
+
+## [おまけ]: 導入
+さて、ここから下は全ておまけだ!
+
+ざっと行くぜ!
+
+## [おまけ - java8 stream]: 他の reduce
+> `reduce`の定義は java8 stream には3つあるけど、
+
+他の2つを紹介する。
+
+1つめはこれ。
+
+```java
+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`がある方
+<img width="720" alt="reduce with zero a.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/4267d77f-846e-c7f3-1185-f5b619cc675f.png">
+
+`T t`がない方
+<img width="720" alt="reduce with head.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/037e077d-e745-7d91-f7c4-aeb12eeadddc.png">
+
+初期値を自分で指定するか、最初の一つを初期値とするかの違いが、`T t`の有無の違い。
+
+で、どうして戻りが`Optional`になってしまうかは、空リストの場合を考えるとわかる。
+
+リストが空なら`T t`を最終結果にできる
+<img width="720" alt="reduce with zero empty.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/5a4ed305-2401-c30f-a204-69066f76d470.png">
+
+`T t`がなくリストも空だとどうにもならない
+<img width="720" alt="reduce with head empty.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/0f6da21c-6e68-deec-d1f6-8627db0421b6.png">
+
+初期値がなくて空リストだと、戻りが用意できないからだ。
+
+## [おまけ - java8 stream]: さらに他の reduce
+残りの1つを紹介する。
+
+2つめはこれ。
+
+```java
+<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); // とりあえず、3つめの引数を忘れる
+T reduce(T t, ((T, T) -> T) f); // 最初の reduce の再掲
+```
+
+謎の3つめの引数を忘れれば、最初の`reduce`とよく似ている。
+
+これは「初期値がリストの型と違っていても畳み込めるよ」という意味であり、他の言語だとまず大体はこの形が標準だ。
+
+<img width="720" alt="reduce with zero b.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/b6b9f8d2-7a14-900a-8fb1-3d7734c485a7.png">
+
+で、最後の3引数めだが、java8 stream は並列実行を考慮しているので分割実行した結果をマージする方法を要求してくる。正直これは隠蔽して欲しい。
+
+<img width="720" alt="reduce with zero java8 stream.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/75c85dd3-dcb6-0be5-c7ba-e1f3b4590c9e.png">
+(内部処理ちゃんと読んでないので、これは本当に「イメージ」)
+
+3引数のは少し抵抗があるかもしれないが、3引数めをノイズだと思えば他の言語と同じなので、避けずに習得しておくと色々と吉。
+
+## [おまけ - java8 stream]: reduce の応用
+`[10, 30, 45, 15]`の総和が知りたいなら`sum`使えば良いじゃん、って考えるのはその通り。
+
+`reduce`は初期値の型が違う場合にこそ価値がある。初期値に違う型が使えれば、実質なんだってできるぞ。
+
+例えば、`(`と`)`の羅列が正しく閉じ合っているかをチェックする、なんて処理も`reduce`でさっと書ける。
+
+```Java
+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)`であれば、`(`と`)`の数は一緒だし、一度も過分に`)`がなかったってことだ。
+
+2つの`Optional`をマージする3引数めは、両方`Optional(n)`であれば中見で加算すれば良い。両方〜〜なら、ってのは`flatMap`だ。これがすぐ出てくると良い感じ。
+
+```java
+U reduce(U u, ((U, T) -> U) f, ((U, U) -> U) g); // 再掲
+```
+
+型とにらめっこしつつ、習得しよう。
+
+## [おまけ - java8 stream]: reduce の初期値の使われるタイミング
+reduce は計算の順番や向きに気をつけないといけないので、さらっと例を載せる。
+
+この2つは同じ結果になる。
+
+```java
+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
+```
+
+けど、この2つの結果は違う。
+
+```java
+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`を見ておこう。
+
+```java
+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 未満のところだけにしてみよう。
+
+```java
+lines
+ .filter(line -> line.contains(":"))
+ .map(line -> Integer.valueOf(line.split(":")[1]))
+ .sorted()
+ .takeWhile(n -> n < 30); // [10, 15]
+```
+
+`takeWhile`は「先頭から特定の条件に合致する間だけ拾う」って感じだ。
+`dropWhile`と合わせて案外よく使うので、これも覚えておくと吉。
+
+<img width="720" alt="take while.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/4ead28ee-c83f-e4a7-8f95-6a7c77c6ea9c.png">
+
+## [おまけ - javaslang]: zip
+最後にもうひとつ、`zip`も案外よく使うので紹介する。こいつも javaslang を使って紹介する。
+
+こいつは2つのリストの同じ箇所をペアリングする様なイメージだ。ジッパーみたいな感じって思うとわかりやすいかも。
+
+```java
+List.of(1, 2, 3)
+ .zip(List.of('a', 'b', 'c')) // [(1, a), (2, b), (3, c)]
+```
+
+<img width="720" alt="zip.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/8680ccce-1ba0-a116-87d6-18e6d23e4be7.png">
+(`zip`は`Tuple<A, B>`という違う型をペアリングできる型がないと使えない。)
+
+`A`と`B`をペアリングしたい場合以外にも例えば、`Integer`のリストのそれぞれの隙間の大きさが知りたいときなんかは、同じリストを1つずらして`zip`してみる、なんてやり方がある。
+
+```java
+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`はお隣さんとの計算ではなくてそこまでの総和(とか)とひとつずつを計算しているから、隙間計算とかは素直にはできない。)
+
+<img width="720" alt="zip resolve.png" src="https://qiita-image-store.s3.amazonaws.com/0/113398/18531170-8f6f-71a6-e93b-22c3c0025d9f.png">
+
+ログファイルなんかを上手く`filter and map`して、`zip`して1行毎の処理時間差分を取って`reverse sort and takeWhile`なんてしてみると、500 ms 以上かかってる行を遅い順に表示する、なんてことができる。
+
+## [おまけ - java8 stream / javaslang]: map のメリット
+「メリットがわからん」「for で良くね?」って話が絶対に出るけど、学習コストに見合うメリットは当然ある。
+
+いくつかあるけど、軽く3つ挙げてみようと思う。
+
+### 1. 状況とやりたいことを分離出来る
+例えば`String -> Integer`のこんな function がある。
+
+```java
+private static Integer toIntAndTwice(String s) {
+ return Integer.valueOf(s) * 2;
+}
+```
+
+この function を「複数の`String`がある場合」、「最大1つの`String`がある場合」、「フォーマット不正かもしれない`String`がある場合」に適用するコードを愚直に書くと、こうなる。
+
+`List`の例
+
+```java
+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`の例
+
+```java
+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`の例
+
+```java
+Integer result;
+
+String org = ...; // "1" or "x"
+
+try {
+ result = toIntAndTwice(org);
+} catch (Throwable t) {
+ result = null;
+}
+
+return result;
+```
+
+`toIntAndTwice`を特定の状況にある`String`に適用するのに、全然違うコードを書かないといけない。
+
+これを`map`で書いてみるとこうなる。
+
+`List`の例
+
+```java
+List<String> org = ...;
+List<Integer> mapped = org.map(JSMain::toIntAndTwice);
+return mapped;
+```
+
+`Option`の例
+
+```java
+Option<String> org = ...;
+Option<Integer> mapped = org.map(JSMain::toIntAndTwice);
+return mapped;
+```
+
+`Try`の例
+
+```java
+Try<String> org = ...;
+Try<Integer> mapped = org.map(JSMain::toIntAndTwice);
+return mapped;
+```
+
+同じ見た目になるね!
+これは「`List`や`Option`の持つ特定の状況におけるルール」と「実際にやりたいこと(`toIntAndTwice`)」が分離されていて、前者が言語にフォローしてもらえているからだ。
+
+ついでに、ここまでコードが似てるともっと共通化出来る気がするね?
+javaslang の`List`や`Option`は`Value`を継承しているので、こんな事もできる。
+
+こんな`Value<T> -> Value<R>`を定義しておけば、
+
+```java
+private static Value<Integer> mapAnyType(Value<String> org) {
+ return org.map(JSMain::toIntAndTwice);
+}
+```
+
+引数が`List`でも`Option`でも動く!
+
+`List`の例
+
+```java
+Value<Integer> m1 = mapAnyType(List.of("1", "2", "3")); // List(2, 4, 6)
+```
+
+`Option`の例
+
+```java
+Value<Integer> m2 = mapAnyType(Option.none()); // None
+```
+
+`Try`の例
+
+```java
+Value<Integer> m3 = mapAnyType(Try.of(() -> "x")); // Failure(java.lang.NumberFormatException: For input string: "x")
+```
+
+これなら同じコードで違う状況が捌けるので、例えば`有料オプションの解約処理`を用意しておいて、「一括で解約する機能(`List`)」、「持っているなら解約する機能(`Option`)」、「持っているはずなので解約する機能(`Try`)」が一気に実現できる。
+
+この「状況」と「処理」の分離が一番のメリットだと思う。
+
+### 2. 一時変数が登場しない
+みんな大好きレガシーコード。こんなのよくあるよね。
+
+```java
+// 初期化
+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;`はテキストとしては同じなのに中身は全く違うよね。(多分、ね。僕も知らん。)
+
+行に前後関係があるのでその行だけコピペしたりできないし、コメントでブロックを作ってる風だけど、実質これは巨大な1ブロックでしかない。
+
+これが例えばさっきのコードみたいになっていると、引数3つの全ての行が独立して機能するし、`return`してはいけない処理中の変数というのがメソッドスコープにない。
+(`;`が1つなので、このコードは1行。なので隙間状態があり得ない。)
+
+```java
+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));
+```
+
+こうなっている方が圧倒的に再利用性が高いし、品質も高いと思う。
+(もちろん共有コードでやるならもう少し丁寧にした方が良いと思うけど。2引数めはちゃんと名前をつけて軽くテストコードも書く、3引数めは`ReduceUtil::mergeOptional`にする、とか。effective java 3 版もそんなことを言っていた気がする。)
+
+### 3. 別の言語の(に)経験が活かせる
+詳細は次で触れるが、考え方自体を知っていればよほど特殊な言語でもない限り初見でも割となんとかなる。
+
+java8 stream を習得して ruby に行ってみればリスト操作はすぐできるだろうし、java8 初心者でも python 経験者なら stream はできるだろう。
+
+## [おまけ]: 単語帳
+直前のメリットでも触れたが、大抵の言語では`map, filter, reduce`は用意されている。
+
+知らない言語を仕事で急遽メンテしないといけない時とか、拾ったツールにちょっと手を入れたいときとかに、単語と処理イメージさえわかっていれば結構なんとかなる。
+なので最後によく聞く言語で同様の処理をする方法をまとめて終わりにする。
+
+(`(*)`が付いている箇所は、上手く使えば似たことが出来るよ、って感じ)
+
+lang | map | filter | reduce(zero / left)<br>reduce(head / left)<br>reduce(zero / right)<br>reduce(head / right) | take while | zip
+:-- | :-- | :-- | :-- | :-- | :--
+java | map | filter | reduce<br>reduce<br>-<br>- | - | -
+groovy | collect | findAll | inject<br>inject<br>-<br>- | takeWhile | transpose (*)
+scala | map | filter | reduceLeft / reduceLeftOption<br>foldLeft<br>reduceRight / reduceRightOption<br>foldRight | takeWhile | zip
+python | map | filter | reduce<br>-<br>-<br>- | itertools.takewhile | zip
+php | array_map | array_filter | array_reduce<br>array_reduce<br>-<br>- | - | array_map (*)
+ruby | map / collect | select | reduce / inject<br>reduce / inject<br>-<br>- | take_while | zip
+js | map | filter | reduce<br>reduce<br>reduceRight<br>reduceRight | - | -
+haskell | map | filter | foldl<br>foldl1<br>foldr<br>foldr1 | takeWhile | zip
+
+`map / collect`, `filter`, `reduce / fold / inject`あたりの単語を覚えておけば、大抵の言語は何とかなるよ、ってこと。
+
+`map vs collect`や`reduce vs inject`は、調べてみると面白いかも。
+
+## おわり
+
+ここまで読んでくれた人がもしいたら、ありがとうございます。
+
+宣言した日にちゃんと記事が間に合って良かった。おしまい。