Haskellへの巡礼

C++の入門書を書くという目的のため、C++を一旦離れてHaskellを学ぶことにしてはや三日目。初日は環境構築で潰れ、二日目はリストを学ぶだけで終わった。

Haskellのリストは、単に順序のある値の集合だけではなく、[1..10]のように規則的な数列を作り出す機能も持っている。またList comprehensionsといって、リストからリストを生成する機能もある。

二日目はリスト処理を学ぶだけでだいぶ疲れた。何も難しいことをしている実感はないのだが、全く馴染みのない新しい概念を学ぶということはかくもつらく苦しいものだとは、久しく忘れていた。馴染みのない新しいことを学ぶのはつかれるということは覚えておかなければならない。

そして三日目はtupleを学んだ。

List comprehensionsはなかなか興味深い機能で、本質的にループであり、imperative languageでループを書いて実装する計算のうちの一部はList comprehensionsで実装できるようだ。

しかし、一部でしかない。そこがつらい。私にとってプログラミングとは、標準入出力と入力で得たものを処理して出力することなので、なにはともかくも標準入出力を扱いたいのだが、Haskellで標準入出力を自在に扱うためには覚えることがまだ色々とあるらしく、まだ手を出すことができないでいる。

四日目。型と型クラスを学び、関数とパターンマッチについて学んでいる。Haskellについて少しわかってきた。

しかし、List Comprehensionsでパターンマッチに失敗した要素は単に無視されるのがとても気に食わない。

xs = [ [1,2], [], [3,4] ]
 [a + b | [a,b] <- xs ]
[3,7]

Haskell 2010 Reportにも書いてあるので受け入れるしかないが。

3.11 p2: and if a match fails then that element of the list is simply skipped over.

まだHaskellの全体像をつかめていないのでHaskell 2010 Reportを本格的に読んでいないが、パターンマッチは3.17で規定されている。まだ知らない知識が多すぎて読めない。

7日目。Higher Order Functionsについて学んでいる。もうHaskellはだいぶ理解できてきた。試しにPandocのコードを読んでみたが、部分的に意味がわかるようになっていた。これならば後は全部学ぶだけだ。

さて、Imperativeな言語であるC++が専門の私がHaskellに思うこととしては、やはり速度だ。

まず最適化だが、sumのようなリストの合計値を計算するコードがあったとして、

accumulate [] = error "empty list."
accumulate [a] = a
accumulate (h:t) = h + accumulate t

このコードは毎回リストが空であるかどうかのパターンマッチが入るので非効率的であるが、リストが空でなければ、その後リストが空になることはないので、賢いコンパイラーならば、空のリストのパターンマッチを最初の一回だけにするように変換できるはずだ。

accumulate [] = error "empty list"

accumulate x = accumulate' x
    where   accumulate' [a] = a
            accumulate' (h:t) = h + accumulate' t

これをcall-pattern optimizationと呼び、Haskellではデフォルト無効で、-fspec-constrもしくは-O2で有効になる。デフォルトで有効になっているべき最も初歩的な最適化のように思える。

Haskellはとても賢いコンパイラーがimperativeな操作を行うように最適化を行えば早くなるだろうが、現状ではそうではない。例えばhaskell.orgのクイックソートの例はひどい。

https://wiki.haskell.org/Introduction#Quicksort_in_Haskell

このHaskellのクイックソートのコードは簡潔でアルゴリズムを学ぶのに最適だが、とても遅い。それに反論するために以下のページがある。

Introduction/Direct Translation - HaskellWiki

曰く、Haskellのナイーブなクイックソート例は遅いので、世の中にはHaskellの拘束なクイックソート例と称するものがいくつも出回っているが、どれもコンパイルできない。

そこで、HaskellでCのクイックソートと同等のコードが示してあるが、Cのコードより長く、Cのコードより読みにくく、そして依然としてCのコードより2倍は遅い。

もはや喜劇もいいところだ。

8日目。再びlistとlist comprehensionsについて考えている。Haskellのリストは、C++でいえば、配列であり、for文であり、std::iotaでもある。遅延評価されて適切に最適化されるのであれば速度も問題ないだろうが、しかしクイックソートの例はひどい。

pattern guardsの存在を知ったので、すべてのパターンマッチはcase式で書けるというHaskell 2010 Reportの記述が確認できた。

Haskell 2010 Reportは少しづつ読み始めているが、至るところで何の言及もなく使われているotherwiseキーワードがないのが気になった。GHCIでotherwise = 0と書いてみると何の問題もなく実行される。試しに:t otherwiseしてみると、どうやらotherwiseとは引数を取らずBoolを返す関数のようだ。なるほど・・・いや、それはもしかして・・・やはり単なるotherwise = Trueか。

9日目。ちょっと学ぶ速度が落ちてしまったがのんびりと入門書を読み続けている。ところで、たまたまPCを再起動したときに、ブート直後のGHCIの初回起動が信じられないほど遅いことに気がついた。プロンプトが表示されるまでに5秒はかかる。次回以降の起動は一瞬だ。一体なぜなのか。大規模なファイルシステムへのアクセスをしていてファイルシステムへのキャッシュの有無なのだろうか。そのコンピューターはM.2 SATA SSDを使っていたが、この仮設を確かめるために、よりストレージ性能の高いM.2 NVMe SSDを搭載した別のコンピューターをリブートしてGHCIを起動してみた。やはり初回起動はプロンプト表示までに2秒ぐらいかかる。

だいたい、言語の習得自体に問題がなくなってくると、こういう些細なところが気になってくる。