「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 クラスには色々と不満がある：

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

続きを読む →

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

コメントを残す

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

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

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

Haskell で高速なプログラムを書くときに注意すること

Haskell は表現力が高いプログラミング言語だが、気をつけないと非効率的なコードが生成されてしまうことがある。では、どういうところに気をつければ高速なコードになるのか。少し調べてみた。

この記事に書くのは、あくまで原則とかそういうやつなので、コンパイラーの最適化（正格性解析、インライン化、自動ボックス化解除）によっては、自前で工夫しても意味がない、つまり、コンパイラーに任せた場合と同じ結果になるかもしれない。どういう場合に早くなるかはケースバイケースなのだ。 続きを読む →

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

1件のフィードバック

Haskell には Num という型クラスがあって、足し算とか掛け算の基本的な演算はここで定義されている。標準ライブラリで定義されているインスタンスとしては、 Int, Integer, Rational, Complex a などがある。

一言で言えば Num クラスは環っぽいものに対応するのだが、いろいろとアレな点がある。これを設計した人は、インスタンスとして整数、有理数、浮動小数点数、複素数くらいしか想定していないのではないか。 続きを読む →