What's new in purely functional data structures since Okasaki?
Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by Okasaki in 1998, but not present in that book) Finger trees (and their generalization over monoids) There are also some interesting ways of implementing already known datastructures, such as using "nested
A Very General Method of Computing Shortest Paths
This post is a literate Haskell file. To follow along, cut and paste the entire text of this post into a file called StarSemiring.lhs and load it up in GHCi. > module StarSemiring where I would like to introduce you to a very general algorithm that I like to call the Gauss-Jordan-Floyd-Warshall-McNaughton-YamadaGauss-Jordan-Floyd-Warshall-Kleene algorithm. With this simple algorithm (an algorithm
Finger Trees Done Right (I hope) | ScienceBlogs
A while ago, I wrote a href="http://scienceblogs.com/goodmath/2009/05/finally_finger_trees.php">couple of posts that claimed to talk about finger trees. Unfortunately, I really botched it. I'd read a bunch of data structure papers, and managed to get myself thoroughly scrambled. What I wrote about was distantly related to finger trees, and it was useful to help understand how fingertrees work - bu
パスを数える simpath algorithm を実装した (Haskell) - 落書き、時々落学
パスを数える simpath algorithm を実装した。knuth先生のあの本にのっているとか。 参考動画 http://youtu.be/Q4gTV4r0zRs simpathは動的計画法(DP)の一種。ただし、そのまま DPの表を作るとメモリ不足とかで頓死するので、動的に表を作成し、不要部分は削除、共有可能な部分は共有するという方針。 それでも、メモリ消費は大きくてHaskellで実装した下のコードでは 9x9 は計算できたけど 10x10 はメモリが足りなくて実行できなかった。工夫すればできそうだけど、そもそもHaskellで書くのがまちが(ry {-# LANGUAGE TupleSections #-} import Data.IntMap (IntMap, insert, insertWith, delete, empty, fromList) import Data.M
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Jonathon Vogel's Blog: Cracking Word Searches with Haskell
Algorithm of the Week: Aho-Corasick String Matching Algorithm in Haskell
