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

[絵で理解するリスト処理 - java8 stream / javaslang -](https://qiita.com/suzuki-hoge/items/16ab07c65f5f906cf600) のおまけ記事！

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

ざっと行くぜ！

## [おまけ - java8 stream]: 他の reduce
> `reduce`の定義は java8 stream には３つあるけど、

他の２つを紹介する。

１つめはこれ。

```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
残りの１つを紹介する。

２つめはこれ。

```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);                     // とりあえず、３つめの引数を忘れる
T reduce(T t, ((T, T) -> T) f);                     // 最初の reduce の再掲
```

謎の３つめの引数を忘れれば、最初の`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">

で、最後の３引数めだが、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">
（内部処理ちゃんと読んでないので、これは本当に「イメージ」）

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

## [おまけ - 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)`であれば、`(`と`)`の数は一緒だし、一度も過分に`)`がなかったってことだ。

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

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

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

## [おまけ - java8 stream]: reduce の初期値の使われるタイミング
reduce は計算の順番や向きに気をつけないといけないので、さらっと例を載せる。

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

```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
```

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

```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 を使って紹介する。

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

```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`のリストのそれぞれの隙間の大きさが知りたいときなんかは、同じリストを１つずらして`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`して１行毎の処理時間差分を取って`reverse sort and takeWhile`なんてしてみると、500 ms 以上かかってる行を遅い順に表示する、なんてことができる。

## [おまけ - java8 stream / javaslang]: map のメリット
「メリットがわからん」「for で良くね？」って話が絶対に出るけど、学習コストに見合うメリットは当然ある。

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

### 1. 状況とやりたいことを分離出来る
例えば`String -> Integer`のこんな function がある。

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

この function を「複数の`String`がある場合」、「最大１つの`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;`はテキストとしては同じなのに中身は全く違うよね。（多分、ね。僕も知らん。）

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

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

```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));
```

こうなっている方が圧倒的に再利用性が高いし、品質も高いと思う。
（もちろん共有コードでやるならもう少し丁寧にした方が良いと思うけど。２引数めはちゃんと名前をつけて軽くテストコードも書く、３引数めは`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`は、調べてみると面白いかも。

## おわり

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

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