D問題を時間内に解けなかった&考えていた方法が想定解と違っていたので供養する。
続きを読む「プログラミング」カテゴリーアーカイブ
Haskellerのためのモノイド完全ガイド
Haskellにおけるモノイドについて解説記事を書いてみた。他の言語でも通用する話があるかもしれないし、ないかもしれない。
続きを読むフィボナッチ数絡みの競プロの問題を解いてみた(Typical DP Contest T)
この間、フィボナッチ数を計算する記事を書いていたら、@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モノイド関手だよ、何か問題でも?」と言って他人を煙に巻くことができます。 続きを読む
SML、はじめました
動機
プログラマーの3大欲求と言えば「プログラミング言語(処理系)を作りたい」「テキストエディターを作りたい」「OSを作りたい」である。これらの欲求は定期的に湧いてきて、多くの場合は実を結ぶことなく霧消する。
そんなわけで先日、筆者にもプログラミング言語の処理系を作りたい欲求が湧いてきた。
具体的には、ML系の型推論を持った言語を作りたい。また、エフェクト推論・リージョン推論のような技法を試したい(一旦普通に処理系を作り、その後に改造してエフェクト推論やリージョン推論を試す)。
別の方向性の動機として、型のないスクリプト言語(具体的にはLua)で大きなソフトウェアを書くのがだるい。静的型のついた言語からスクリプト言語にコンパイル(トランスパイル)するやつを作りたい、というものがある。
最近はJavaScriptへトランスパイルする処理系は色々登場したが、それ以外のスクリプト言語を吐き出す処理系というのはまだ少ないように思う。
これらの動機付けが混ざった結果、「型推論のある言語からスクリプト言語へのコンパイラーを作れば良い」という結論に至った。 続きを読む
TeX Live 2018でWindows上のTeXworksが日本語を含むファイル名を扱えない話
タイトルの件である。(実際にはTeXworksは問題の核心に1ミリも関係しないので、TeXworksを使っていないあなたもこの記事を読み物として楽しむことができる。さあ読もう)
この記事を書いている6月現在、TeX Live Managerで最新版にアップデートすれば問題は解決するはずである。
この記事では、筆者がどのようにこの問題の原因を突き止めたか、順に書き連ねていく。なお、問題の発覚と原因究明は5月初めに行ったが、TeX Liveのアップデートで対策されるようになるのを待った結果記事の公開が6月になった(筆者がよくブログ記事を下書きのままほったらかしているのとは関係ない)。 続きを読む
GLMのマニュアルがヘボいので自分で書き始めた
GLM — OpenGL Mathematics というC++のライブラリーがある。これはOpenGLとかで使うようなベクトルや行列の型・関数を提供してくれる。
それはいいのだが、これ、ドキュメントがヘボい。
まず公式の Manual は、ライブラリーの使い方を説明してくれるが、個々のAPIには立ち入らない。
次にDoxygenで生成された API Documentation は、個々の関数の説明をしてくれるが、(ベクトルとか行列の)型の説明が欠けている。そして、「ソースコードに飛ぶ」をやっても関数の実装は見れない(.hppはDoxygenの対象に入っているが.inlは入っていない)。関数がどういう数式を基に実装しているのか、GLMのドキュメントからはわからないのである。
まあGLMはGLSL互換を謳っているので、GLSLを知っていれば(GLSLのドキュメントを読めば)細かい説明はなくても使えるだろうという考えもあるかもしれない。それはまあそうかもしれないが、GLSLにないGLMの拡張機能に関してはそういうわけにはいかない。
たとえば、四元数に関連した mat4_cast 関数のドキュメントには
GLM_FUNC_DECL mat<4, 4, T, Q> glm::mat4_cast ( tquat< T, Q > const & x )
Converts a quaternion to a 4 * 4 matrix.
Template Parameters
T Floating-point scalar types.
See also
GLM_GTC_quaternion
とあるが、果たしてこの説明から関数の動作を予想できる人がどれだけいるだろうか?
したがって、(コピペコーディングではなく)GLMをまともに使おうとしたらGitHubのソースコードをチマチマ眺める必要があるわけだが、そんなのは辛すぎる。というか、LaTeXでもMathJaxでもいいから、数式をふんだんに使ったGLMのマニュアルが欲しい…。
というわけで、自分で書いてみることにした。
https://miz-ar.info/glm-notes/
現段階ではまだ、クォータニオン(四元数)についてちょろっと書いた程度である。筆者の必要に応じて、徐々に拡充していきたい。
なんとなく英語で書いてみているが、文法とか色々怪しいのでその辺はご容赦願いたい。
glm-notes/ 以下のURLは今後変わるかもしれないので、リンクを貼るならトップページ(https://miz-ar.info/glm-notes/)にお願いしたい。
なお、C++の関数の型は(伝統的には)戻り値の型を先に書くが、自分の書いたドキュメントでは(筆者にとっての読みやすさのため)戻り値の型は後置とする。また、引数の型の const&
も省く。
おまけ
GLMとは全く関係ないが、筆者のほしい物リストとほしい本リストを公開しておく。今月は筆者の誕生月である。
関連記事
wxWidgets をビルドする 2018年新春編
去る2月に、wxWidgets の開発版である 3.1.1 がリリースされた。前回の開発版である wxWidgets 3.1.0 のリリースからは2年ぐらい経っている。
2016年に wxWidgets をビルドする という記事を書いたが、2年も経つとビルドシステムにも色々と変化が生じている。この記事では、3.1.1リリース直後の現在(2018年3月)における、 wxWidgets の最新の開発版(3.1.1 または Git の master ブランチ)のビルド方法をまとめてみる。
(筆者が記事を書くのにもたついている間に、最新の安定版である 3.0.4 もリリースされたが、この記事はもっぱら最新の開発版を対象とする。) 続きを読む
PureScript から TypeScript 用型定義 (.d.ts) を生成するツールを作った
前置き
TypeScript で作っていたプロジェクトに、後付けで PureScript を追加しようとしたらかなり辛かった。
(わざわざ言語を混在させたい理由としては、型クラスや演算子オーバーロードを使いたい&既存のコードを全部書き直す暇はない、が挙げられる)
辛い理由としてはそもそもモジュールとバンドラーの周辺がまだ成熟していないというのもあるだろうが、 TypeScript 固有の理由として、 TypeScript コードから PureScript モジュールを読み込むための型定義が足りないという問題がある。
Stack Overflow を見ると、同じことで悩んでいる人がいた:
しかし、どの解決策もイマイチである。
コンパイル済みの PureScript を使うだけなら --allowJs
オプションという手もあるだろうが、せっかく型がある言語で書いたのだから、適切な型チェックがされて欲しい。PureScript のコンパイル時に TypeScript 用の型定義ファイル .d.ts
を出力させるようにはできないのか?
PureScript の GitHub Issues にも「.d.ts を生成させたい!」というトピックがあるが、特に動きがあるようには見えない。
コンパイラーにそういう機能がないならば、自分で作ってしまおう!ということで、作った。