2017-12-20

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秒ぐらいかかる。

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

7 comments:

しげ♪ said...

list comprehension は実際にはあまり使われてません。コーディングガイドラインでも、使わないほうがいい機能として扱われてます。

https://wiki.haskell.org/Programming_guidelines#List_Comprehensions

なのであんまりこだわらない方がいいかもです。

Anonymous said...

デフォルト無効になっているのはコンパイル時間がなぁ・・・
動作確認のためのコンパイルのたびにエスプレッソを入れるわけにもいかず、最終的な成果物を取り出すときにのみ-O2するなり覚悟して常にコンパイル時間を受け入れるかというところ そうでなくても実際に吐き出すバイトコードと大きくかけ離れた言語仕様はコンパイル時間の長大を招くので仕方ないのではとは
また、ソートについてはもともとイミュータブルな連結リストが標準であるためクイックソートを使うこと自体が効率的なのかとは GHCのライブラリに存在するSortの実装は木構造を組み立ててつぶすHeapソートになっています

Anonymous said...

今のコンパイラがどこまで解釈するかわからないけど、一般的に再帰処理で速度を求めるなら、末尾呼び出し形式に変形することが最優先ではないですか。

accumulate lst = accumulate' 0 lst
where accumulate' total [] = total
accumulate' total (h:t) = accumulate' total + h t

エヌユル said...

> 今のコンパイラがどこまで解釈するかわからないけど、一般的に再帰処理で速度を求めるなら、末尾呼び出し形式に変形することが最優先ではないですか。

デフォルト遅延評価のHaskellでは末尾呼び出し形式が高速であるとは限りませんし,そもそもそのコードは末尾呼び出しではありません

Anonymous said...

> デフォルト遅延評価のHaskellでは末尾呼び出し形式が高速であるとは限りませんし,そもそもそのコードは末尾呼び出しではありません

型と処理を考えれば、括弧を入れ忘れてるだけでtail callですよ。

accumulate' total (h:t) = accumulate' (total + h) t

あと

- https://wiki.haskell.org/Performance/Accumulating_parameter

では、やはりtail callにするほうが速いとなっていますけれど、どの世界の話でしょうか。

エヌユル said...

accumulate' total + h tを(accumulate' total) + (h t)と読んでいました.
Haskellの文法的に考えてそのように読んで,即座にそう思ったのですが,型を考えると,確かに貴殿が括弧を入れ忘れていることを推測してあげるべきでしたね.
括弧の入れ忘れを推測してあげられなくてごめんなさい.

末尾再帰が速いと限らないという世界の話は「余再帰」でググってください.
正直言って最適化の話は専門ではないし興味もあまり無いので自信はないです.
後私は英語が読めません.

opbest said...



Thanks for sharing your info. I really appreciate your efforts and
I am waiting for your next write ups thanks once
again.

Here's my website : -- 강남안마

(freaky)