あどけない話

Internet technologies

2012-11-01から1ヶ月間の記事一覧

型クラスとモナドと Free モナド

要約:Free モナドは何が嬉しいのかを議論するためのたたき台。以下の2つの論文に載っている例を3つの方法で実装する。 Janis Voigtlander, "Asymptotic Improvement of Computations over Free Monads" Wouter Swierstra and Thorsten Altenkirch, "Beauty …

なぜ Haskell ではキューが軽んじられているか?

Haskell ではキューが欲しくなったら Data.Sequence を使えと言われる。Seq は両端キューだし、シーケンスとして使えば、連結(>finger treeなのでコードが複雑なのと、計算量が「ならし」なところが玉に傷である。もっと単純で、最悪計算量を保証する(両端で…

PFDS 10.3 Trie

Trie は、分岐のみで値を持たないノードを許す多分木。 Radix tree(Patricia)は、すべてのノードに値を持つ多分木。各ノードはキーの差分を持つ。 Trie 本のコードは抽象的過ぎて分からないので、3ステップで理解する。 素朴に Map を使う Trie Map を型変数…