Haskell」カテゴリーアーカイブ

Haskellでの浮動小数点数の方向付き丸めを考える

週刊 代数的実数を作る」の #5 で、区間演算と方向付き丸めの話を書いた。浮動小数点数の計算は不正確だと思われがちだが、方向付き丸め等をうまく使えばある種の「正しい結果」(この数は確実に1.0より大きい、等)を得ることができる、という話だ。

MPFRのようなソフトウェア実装の浮動小数点数だと引数で丸めモードを指定できる。しかし、ハードウェア組み込み(注)の浮動小数点数(floatやdouble)の丸めモードを指定する方法は、言語や実行環境に依存する。

(注:環境によってはCPUに浮動小数点演算器が組み込まれておらず、floatやdoubleの演算もソフトウェア実装だったりするが、我々が普段使うPCではfloatやdoubleはほぼ確実にハードウェア実装されているため、以下「ハードウェア実装」で通す)

CやFortranのような低レベルかつ数値計算のニーズがあるようなプログラミング言語だと、丸めモードを変更する手段が用意されているが、JavaScriptやHaskellなど、そういうニーズが薄い言語では丸めモードの変更には対応していないことが多い。せいぜい、「浮動小数点数演算には最近接丸めを使用する」と規定されているのが関の山である。

しかし、「Haskellではできない処理がある」というのはどうにも気にくわない。どうにかして、ハードウェア組み込みの浮動小数点数の方向付き丸めをHaskellで扱う方法を考えたい。

ちなみに、ハードウェア組み込みの浮動小数点数にこだわらないのであれば、MPFRの丸めモード指定を使うHaskellライブラリーがすでに存在する:

http://hackage.haskell.org/package/rounded

続きを読む

HaskellでAtCoderに参戦して水色になった

3月下旬からAtCoderのRatedコンテストに参加しています(AtCoderプロフィール)。この度、5月26日のABC128でようやく水色になりました(AtCoder社長の記事によると、これは上位15%に相当するらしいです)。

使用言語はHaskellです。コンテストの時間中に提出したコードは全てHaskellだったと思います。

この記事では、Haskellを使う理由や、Haskellで競技プログラミングをするコツ、AtCoderでHaskellを使う際のアレコレなどを書いていきます。「水色になるための方法」みたいな話はしません(できません)。

続きを読む

最速のフィボナッチ数計算を考える

Qiitaにこういう記事を書いた:

Haskellでフィボナッチ数列 〜Haskellで非実用的なコードを書いて悦に入るのはやめろ〜

↑の記事ではメモ化しない計算法が遅いこと、Haskellには遅延評価の罠があって正格にすると早くなること、「n番目のフィボナッチ数」をピンポイントで計算する場合は(行列またはQ(√5)の)冪乗を使う方法が早いこと、一般項(ビネの公式)をその辺の浮動小数点数で計算するのは使い物にならないこと、などを述べた。

まあ、「Haskellでは fib 0 = 0; fib 1 = 1; fib n = fib (n-1) + fib (n-2) でフィボナッチ数が計算できます!」に対する注意喚起としてはこれで十分すぎる内容なのだが、「n番目のフィボナッチ数をピンポイントで計算する方法」についてはもっと深掘りできる。

この記事では、数学的な考察も交えて、「n番目のフィボナッチ数をピンポイントで計算する方法」をより高速化してみたい。(計算量としてはどっちみち O(log n) くらいなのだが、定数倍の部分で高速化する)

なお、記事タイトルには「最速の」と書いたが、この記事で紹介するアルゴリズムが最速だと主張するわけではない(筆者の知らない、もっと早いアルゴリズムが存在するかもしれない)。 続きを読む

アプリカティブ関手ってなに?モノイド圏との関係は?調べてみました!

この記事は Category Theory Advent Calendar 2018 7日目 かつ Haskell (その2) Advent Calendar 2018 7日目の記事です。

Category Theory Advent Calendar 2018の6日目はcorollary2525さんの「随伴は あらゆるところに 現れる」、8日目は空席、9日目はt_uemura669101さんの「トポスと高階論理」です。

Haskell (その2) Advent Calendar 2018の6日目は空席、8日目はtakoeight0821さんの「Type defaultingについての初級的な解説」です。

この記事はどういう記事か

圏論の方から来た人向け:

デカルト積やテンソル積の一般化である「モノイド積」の話と、「内部ホム」の話をします。文献によっては内部ホムはモノイド積の右随伴として導入されますが、ここではモノイド構造を仮定せずに内部ホムの定式化(閉圏)をします。

Haskellの方から来た人向け:

この記事ではHaskellにおけるアプリカティブ関手の使い方は解説しません。Haskellの方から来た読者はすでにアプリカティブ関手をある程度知っており、圏論的な話にチョット興味がある、と仮定します。

これを読めば、「モナドは自己関手の圏におけるモノイド対象だよ、何か問題でも?」と同じノリで「アプリカティブ関手はモノイド圏における強laxモノイド関手だよ、何か問題でも?」と言って他人を煙に巻くことができます。 続きを読む

Haskell でのデバッグ手法あれこれ

プログラムにバグはつきものです。強力な型システムを備えている Haskell でもそれは同じです。この記事では、 Haskell プログラムのデバッグ手法をいくつか挙げてみます。

なお、使用している GHC は 8.2.2 です。より新しいバージョンで追加されるであろうより便利な機能は、この記事の対象外です。

続きを読む

Haskell でオレオレ Num クラスを作るための考察

以前の記事に書いたように、 Haskell 標準の Num クラスには色々と不満がある:

Haskell の Num クラスに対する不満

結論としては「過去に遡って Num クラスの定義を変えるしかない」だったわけだが、時間干渉も因果律への反逆もできない我々としてはその選択肢は現実的ではないので、独自の Num クラス(オレオレ Num クラス)を作ることにする。この記事は、筆者がオレオレ Num クラスを作った際に考えたことをまとめたものである。

続きを読む

Haskell (GHC) の型レベル自然数とリフレクションを試してみる

【2020年4月20日追記】GHCの型レベル自然数については、より網羅的な記事を書いた。型レベル自然数についてより詳しく知りたい方は、こちらの記事も参照いただきたい:GHCの型レベル自然数を理解する【追記終わり】

最近のGHCでは、自然数をパラメーターとするデータ型を定義できる。固定長リストの長さを型に持たせるとか、行列の大きさを型に持たせるとか、そういうことができる。あるいは、自然数 m に対して Z/mZ を表す型を作ることもできる。m を素数とすればこれは有限体となる。

実際に、型レベル自然数を使って Z/mZ に相当する型を作ってみよう。(名前は FiniteField とした) 続きを読む