3月下旬からAtCoderのRatedコンテストに参加しています（AtCoderプロフィール）。この度、5月26日のABC128でようやく水色になりました（AtCoder社長の記事によると、これは上位15%に相当するらしいです）。
使用言語はHaskellです。コンテストの時間中に提出したコードは全てHaskellだったと思います。
この記事では、Haskellを使う理由や、Haskellで競技プログラミングをするコツ、AtCoderでHaskellを使う際のアレコレなどを書いていきます。「水色になるための方法」みたいな話はしません（できません）。
続きを読むHaskellにおけるモノイドについて解説記事を書いてみた。他の言語でも通用する話があるかもしれないし、ないかもしれない。
続きを読むこの間、フィボナッチ数を計算する記事を書いていたら、@fetburner氏にこういう問題を教えて頂いた：
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モノイド関手だよ、何か問題でも？」と言って他人を煙に巻くことができます。 続きを読む
プログラマーの3大欲求と言えば「プログラミング言語（処理系）を作りたい」「テキストエディターを作りたい」「OSを作りたい」である。これらの欲求は定期的に湧いてきて、多くの場合は実を結ぶことなく霧消する。
そんなわけで先日、筆者にもプログラミング言語の処理系を作りたい欲求が湧いてきた。
具体的には、ML系の型推論を持った言語を作りたい。また、エフェクト推論・リージョン推論のような技法を試したい（一旦普通に処理系を作り、その後に改造してエフェクト推論やリージョン推論を試す）。
別の方向性の動機として、型のないスクリプト言語（具体的にはLua）で大きなソフトウェアを書くのがだるい。静的型のついた言語からスクリプト言語にコンパイル（トランスパイル）するやつを作りたい、というものがある。
最近はJavaScriptへトランスパイルする処理系は色々登場したが、それ以外のスクリプト言語を吐き出す処理系というのはまだ少ないように思う。
これらの動機付けが混ざった結果、「型推論のある言語からスクリプト言語へのコンパイラーを作れば良い」という結論に至った。 続きを読む
プログラムにバグはつきものです。強力な型システムを備えている Haskell でもそれは同じです。この記事では、 Haskell プログラムのデバッグ手法をいくつか挙げてみます。
なお、使用している GHC は 8.2.2 です。より新しいバージョンで追加されるであろうより便利な機能は、この記事の対象外です。
コンピューター上で実数を取り扱うには、いくつかの方向性がある。普通は浮動小数点数によって近似することが多いと思うが、多倍長計算を始めとする、「コストをかけてでも正確に」計算するという方向性もある。
そのような「正確に取り扱える」実数のクラスとしては、整数（多倍長整数）や有理数はある程度普及していると思う（標準で備えているプログラミング言語がある）。それよりも広いクラスとして、代数的実数、つまり（整数または有理数係数）代数方程式の根となるような実数全体、というものがある。
代数的実数が計算機で取り扱えるということ自体は割と知られた事実だと思うが、実装は割と大変で、工夫の余地がある。有理数のように「GCD さえ実装すればよい」というものではない。
かくいう私も最近までその辺を真面目に勉強しようとは思っていなかったわけだが、何となくモチベーションが湧いてきたので、代数的実数に関するアルゴリズムを勉強しつつまとめたものを記事として Web 公開してみようかと思った次第である。
実装には筆者の好みで、 Haskell を使う。実際のところ、 Haskell による代数的実数の実装は既にあるようだが、まあ気にしない（自身の勉強が主目的なので）。
というわけで、以下のページで公開している：
https://miz-ar.info/math/algebraic-real/
「週刊」と名乗っているが、毎週末に更新することを目指している。果たしていつまで続くかは不明である。 続きを読む
Haskell で CGI を書いてみよう。 続きを読む