Re: Java8 Streamではクイックソートが書けない

2013-11-22

TL;DR: C#erのドヤ顔は大変みっともない。

Javaのコレクション (もっといえばIterable) とStreamは別の型で、互換性がありません。（必要に応じて相互変換して使う必要があります）。

これはなんでかというと、今更Iterableインターフェースにfilterやらmapやらを生やすわけにはいかなかったからですね。

あれ、Java8ではインターフェースにデフォルト実装を持てるんじゃなかったっけ（filterやらmapやらにデフォルト実装を与えておけばよかったんじゃね？）と思って、java.util.stream.Stream<T>を見てみたら、filterやmapにはデフォルト実装がないですね。設計判断があったんだと思います。

ちなみにC#では、JavaでいうfilterやらmapやらのしくみはC# 3.0のLINQのときに取り込まれてます。LINQの.対象はIEnumerable<T>で、これはC# 2.0のジェネリクス対応の時からある型です。C#の配列とジェネリックコレクションはすべてこのインターフェースを実装しています。んで、なんでLINQ対応できたのかというと、拡張メソッドという仕組みを入れたからです。これは、別の型で後から定義した静的メソッドを、元の型のインスタンスメソッドみたいに呼びだせる、というものです。むりやりJavaにたとえるなら、インターフェースメソッドのデフォルト実装を後付できる機能、みたいな感じでしょうか。なので、IEnumerable<T>インターフェースにfilterやらmapやらを生やさなくて済んだわけです。

で、クイックソートの話。

Javaでも、List<T>に対してじゃなく、Stream<T>に対してクイックソートを書いたりできるんじゃないかと思うわけです。

きしださんのコードを元にするんだけど、Streamにはsizeやらgetやらがないから、そこは書き換えて

public static Stream<Integer> quickSort(Stream<Integer> stream){
    Optional<Integer> pivot = stream.findFirst();
    Stream<Integer> rest = stream.skip(1);
    boolean restIsEmpty = !(rest.findFirst().isPresent()); // isEmpty()ってないんでしたっけ

    return restIsEmpty ? stream :
        concat(
            concat(
                quickSort(rest.filter(i -> i < pivot.get())),
                stream.limit(1)), // pivot
            quickSort(rest.filter(i -> i >= pivot.get())));
}

みたいな感じですか。

そうすると今度は、

• http://d.hatena.ne.jp/siokoshou/20070401
• http://d.hatena.ne.jp/NyaRuRu/20070401
• http://d.hatena.ne.jp/siokoshou/20070402

みたいな、「なんでstreamを何度も評価するんだおめーは！」みたいな話になるわけですが。それはC#が6年前に通った道だ！（ﾄﾞﾔｧｧ）

ん？基本型を扱うStream？C#ならふつうにIEnumerable<int>で大丈夫ですよ？（ﾄﾞﾔｧｧ）