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モノイド関手だよ、何か問題でも?」と言って他人を煙に巻くことができます。 続きを読む

SML、はじめました

動機

プログラマーの3大欲求と言えば「プログラミング言語(処理系)を作りたい」「テキストエディターを作りたい」「OSを作りたい」である。これらの欲求は定期的に湧いてきて、多くの場合は実を結ぶことなく霧消する。

そんなわけで先日、筆者にもプログラミング言語の処理系を作りたい欲求が湧いてきた。

具体的には、ML系の型推論を持った言語を作りたい。また、エフェクト推論・リージョン推論のような技法を試したい(一旦普通に処理系を作り、その後に改造してエフェクト推論やリージョン推論を試す)。

別の方向性の動機として、型のないスクリプト言語(具体的にはLua)で大きなソフトウェアを書くのがだるい。静的型のついた言語からスクリプト言語にコンパイル(トランスパイル)するやつを作りたい、というものがある。

最近はJavaScriptへトランスパイルする処理系は色々登場したが、それ以外のスクリプト言語を吐き出す処理系というのはまだ少ないように思う。

これらの動機付けが混ざった結果、「型推論のある言語からスクリプト言語へのコンパイラーを作れば良い」という結論に至った。 続きを読む

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

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

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

続きを読む

「週刊 代数的実数を作る」創刊

コンピューター上で実数を取り扱うには、いくつかの方向性がある。普通は浮動小数点数によって近似することが多いと思うが、多倍長計算を始めとする、「コストをかけてでも正確に」計算するという方向性もある。

そのような「正確に取り扱える」実数のクラスとしては、整数(多倍長整数)や有理数はある程度普及していると思う(標準で備えているプログラミング言語がある)。それよりも広いクラスとして、代数的実数、つまり(整数または有理数係数)代数方程式の根となるような実数全体、というものがある。

代数的実数が計算機で取り扱えるということ自体は割と知られた事実だと思うが、実装は割と大変で、工夫の余地がある。有理数のように「GCD さえ実装すればよい」というものではない。

かくいう私も最近までその辺を真面目に勉強しようとは思っていなかったわけだが、何となくモチベーションが湧いてきたので、代数的実数に関するアルゴリズムを勉強しつつまとめたものを記事として Web 公開してみようかと思った次第である。

実装には筆者の好みで、 Haskell を使う。実際のところ、 Haskell による代数的実数の実装は既にあるようだが、まあ気にしない(自身の勉強が主目的なので)。

というわけで、以下のページで公開している:

https://miz-ar.info/math/algebraic-real/

「週刊」と名乗っているが、毎週末に更新することを目指している。果たしていつまで続くかは不明である。 続きを読む