にせ末尾再帰 - あどけない話
これはHaskellスペースリーク Advent Calendar 2015の8日目の記事です。 IOのコードは、普通に書けば末尾呼び出しの最適化が効く形になる。たとえば、こんな感じ： foo :: Char -> String -> IO Int foo a b = do c <- bar a b zoo b c woo c woo :: Int -> IO Int woo c = do d <- goo c return $ d + 1 foo が woo を呼び出す時は、fooのフレームを忘れてしまってよい。IOの文脈で再帰関数を書く場合も末尾再帰で十分な場合が多い。 goo :: Int -> IO () goo 0 = return () goo n = do getChar >>= putChar goo (n - 1) 残念なことに、一見末尾再帰に見えるが実はそうなっていなく
Haskellの配列でクイックソート - あどけない話
Haskell の クイックソート としては、以下のようなコードがよく例に出てきます。 quickSortList :: [a] -> [a] quickSortList [] = [] quickSortList (x:xs) = quickSortList lt ++ [x] ++ quickSortList gt where lt = filter (<x) xs gt = filter (>=x) xs これは、小さなリストを何度も連結するので、効率が悪そうです。 そこで、一旦配列に直し、固定領域を使ってソートして、またリストに戻す方がいいのではないかと思い、実装して速度を比べてみました。配列を使うクイックソートのコードは、「珠玉のプログラミング」から拝借しました。ベンチマークも含むコードは、gist に上げています。 結果はこんな感じ(単位はms)： 入力のサイズ 10^4 10
永続二色木 - あどけない話
Purely Functional Data Structures の勉強会で説明した二色木(Red-black tree)に関するメモ。 Purely Functional Data Structures 作者: Chris Okasaki出版社/メーカー: Cambridge University Press発売日: 1999/07/01メディア: ペーパーバック購入: 5人 クリック: 46回この商品を含むブログ (25件) を見る Sedgewick らが発明した二色木は、もともと短命データとして設計されている。ある木に要素を挿入すると、赤が連続する、つまりバランスが崩れることがある。バランスを回復するときに、破壊的代入を最小限に抑えるために、複雑な作業を施さないといけない。 赤-赤と続く要素の下側を自分だと考える。すると、Sedgewick らのアルゴリズムでは、「伯父」の色も考
書評：Scala スケーラブルプログラミング 第2版 - あどけない話
Scala の作者である Odersky らが書いた「Scala スケーラブルプログラミング」の第2版が出版されました。 Scalaスケーラブルプログラミング第2版 作者: Martin Odersky,Lex Spoon,Bill Venners,羽生田栄一,水島宏太,長尾高弘出版社/メーカー: インプレス発売日: 2011/09/27メディア: 単行本（ソフトカバー）購入: 12人 クリック: 235回この商品を含むブログ (46件) を見る 僕は Haskeller で Scala は初心者です。その僕から見て、この本は本格的で良質な関数型言語の入門書に仕上がっています。特に、関数型言語を学びたい Java プログラマーに、この本をお勧めします。 この本は分厚いので、敬遠したくなるかもしれませんが、それぞれの章は小さくまとめられており、内容もこなれています。訳もよいので、案外すらすら
Haskellの神話 - あどけない話
Haskell の優雅さを示すためによく使われるコードは、優雅さと分かりやすさだけに特化しており、現実的には遅いことが多い。書き手は他に効率のよい実装があることを知っているのだけれど、読み手はそうではないから、後で効率が悪いと気づいて愕然とするみたいだ。 この記事では、神話になっている例を3つ取り上げ、効率のよい実装と合わせて紹介する。その 3 つの例とは、以下の通り。 フィボナッチ数 素数生成 ソート フィボナッチ数 遅延評価を活かした優雅なフィボナッチ数の実装は、以下の通り。 fib n = fibs !! n fibs = 0 : 1 : zipWith (+) fibs (tail fibs) Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」はとても遅いにも書かれているように、この実装は遅い。 その理由は、(+) の計算が遅延し、その待機
言語表現法講義 - あどけない話
言語表現法講義 (岩波テキストブックス) 作者: 加藤典洋出版社/メーカー: 岩波書店発売日: 1996/10/08メディア: 単行本購入: 9人 クリック: 96回この商品を含むブログ (50件) を見る 文章の書き方をテーマとした名著に出会うと、心の中に爽やかな風が吹き抜けていく。こんな風に文章を書けるようになりたいなと。 この本を読んで吹いた風は、爽やかではなかった。熱風に吹き飛ばされそうになった。 この本は、9年に渡る大学での講義録である。熱風の源は、著者の態度にある。学生と真剣に向き合っているのだ。 なぜ最近の学生は文章を書くのが嫌いか。その理由がすぐにわかった。なぜかというと、いくら書いても教師がこれをしっかり読まないからだ。 この授業では、学生の書いた文章を著者が読み授業で批評する。ときには厳しく批判し、ときには「これはちょっと僕には書けない文章だ」と褒める。 私が大学の先生
文章の書き方 - あどけない話
2006年に IIJ の新人研修で「文章の書き方」という講義を担当しました。そのときの資料を何人もの人に個別に差し上げていたのですが、それも面倒になってきました。新人研修の担当者に問い合わせたところ、公開しても問題ないとのことでしたので、資料を公開します。 「文章の書き方」の資料
プログラマの壁 - あどけない話
プログラマに向いている人と向いていない人がいるそうです。 Jeff Atwood さんの「どうしてプログラマに・・・プログラムが書けないのか?」： プログラムを書ける者とプログラムを書けない者の間にある大きな溝についてはよく知られているが、プログラマの職に応募してくる人間は、すでにこの溝を飛び越えているものだとばかり思っていた。明らかにこれは妥当な仮定ではないらしい。プログラムを書けないプログラマの面接で時間を無駄にしないために、FizzBuzzスタイルのふるい分けが必要ということだ。 どんなことでも向き不向きはあるでしょうから、これには納得いきます。しかし、プログラマになれる人の中にも、溝があるようです。 Joel Spolsk さんの「Javaスクールの危険」： 私のささやかな経験から言わせてもらうと、伝統的に大学のコンピュータサイエンスのカリキュラムで教えられているもので、多くの人が
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
