早いもので、今年も12月25日となりました。メリークリスマス！ うちのちびっ子怪獣たちも、サンタさんに書いた手紙通り、レゴをもらってご満悦のようです。そして今日は、Haskell Advent Calendar 2013 の最終日でもあります。 Haskellらしい？ 「純粋なコー…

お茶の水女子大学 理学部 情報科学科 准教授 浅井健一さんインタビューを読んで、思い出しだので書いておきます。デザインレシピを使ったプログラミングを実践するなら Haskell が最適です。以下に簡単な例を示します。 目的 作成するプログラムが何をするの…

Updated on 4 Dec 2013.I upgraded to Mavericks and Xcode 5. There is still "gcc" but it is in fact "clang": % which gcc /usr/bin/gcc % gcc --version Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include…

これまで Twitter でさんざん間違った情報を流してきましたので、反省して正しい情報を書いておきます。おそらく、これで間違いないです。 GHC 7.8 自体 GHC 7.8 自体は動的リンクされます ちなみに、GHC 7.8 から、GHC 自体が -O2 でコンパイルされます。(…

cabal 1.18 のサンドボックスがどういう機能か知らない人は、An Introduction to Cabal sandboxes か 2013年8月現在のHaskell開発環境をどうぞ。それで、sandbox サブコマンドの--sandbox オプションが早速役に立ったというお話。 --sandbox オプション パッ…

GHCのコンパイル速度は、お世辞にも速いとは言えないのだが、一番イライラするのはリンクが遅いこと。これは GNU ld が遅いからである。という訳で、速いと言われる gold を使うためのメモ。GHC 7.6.3 までは gold が使えない。なぜなら、GNU ld 固有のオプ…

以前、僕が実装している web サーバ Mighty が、Haskell で書いているにも関わらず、セグメンテーションフォールトを起こしていた。調べたところ hashable ライブラリがリンクする C の DJBX33X が、SipHash に変わったことが原因だった。このときから SipHa…

ThreadScope は、GHC が生成する event log を可視化ツールです。以前、試行錯誤して Mac にインストールしたときのメモが出て来ました。並列並行本が出版された今、需要が高いような気もするので、公開しておきます。Parallel and Concurrent Programming i…

理解が深まれば、適宜更新します。 G-machine グラフ簡約のためのスタックマシン 関数適用が連なる spine (背骨)を持ち、愚直にカリー化を実現する 簡約のたびに、それぞれの項を更新 ローカル関数はラムダリフティングしてグローバル関数に直す必要がある …

端的に説明するなら「正しく型付けされた項はおかしくなることがない」ことを学ぶための壮大な本。型に関する圧倒的な知識を持ち、説明がうまく、根気づよい人にのみ記すことができた英語の良書が、型システムを愛する訳者と監訳者、および(書中に名前が出て…

適宜追加します。 Pro Git 僕が読んだ Git の書籍の中では、一番分かりやすいと思いました。日本語版の書籍はありませんが、オンライン版が翻訳されています。 Pro Git 図解 Git Git の初心者が動作を理解するのにおススメ。 図解 Git こわくない git ブラン…

注意：github に移動しました。再帰ドリル(1)を読んでいない人は、先に読むこと。 等差数列の和 差が1の等差数列の和を素朴な再帰で実現すると以下のようになった。 soap 0 = 0 soap n = soap (n-1) + n プログラミング言語の内部をよく知っている人は、何度…

注意：github に移動しました。再帰を学ぶためのドリル。使用するプログラミング言語は Haskell。このシリーズは続くかもしれないし、途中で挫折するかもしれない。乞うご期待！ 等差数列の和 差が1の等差数列の和を計算する関数 soap(sum of arithmetic pro…

Haskell には、以下のような時間用の型がある。この記事は、どれを使えばいいかの解説。 time ライブラリの Data.Time.Clock の UTCTime old-time ライブラリの System.Time の ClockTime base ライブラリの System.Posix.Types の EpochTime UTCTime 速度を…

代数データ型(バリアント)をラムダ式で表現する方法の備忘録。ラムダ式を表現するのに、実行可能な Haskell の無名関数を使う。間違いの指摘を歓迎します。こんな感じ： \x y z ... f g h ... -> 引数をうまく組み合わせる x y z ... の部分が、直積を表す f…

見ろ！ Haskell が OOPL のようだ！ さてさて、ようやく重い腰を上げて、Lens を勉強し始めましたよ。Haksell for allを見て勉強すればいいのかなと思ったんですが、解説しているパッケージが data-lens なので古いですね。今、使うべきなのは、lens という…

僕はよく「関数プログラミングの入門書には何がいいか」という質問を受ける。そのときは必ずこの本(と他のいくつか)を答えるようにしている。書評を書いたつもりになっていが、検索してみると書いてないようなので、反省して良書を紹介してみようと思う。プ…

「プログラムのテストはバグの存在を示すことにかけてはとても効率的な方法ですが、バグの不在を示すことにかけては絶望的なほどに不適切です。プログラムの信頼性を顕著に向上させる唯一の方法は、その正当性に対して説得力のある証明を与えることです」 --…

およそ20年前にAlan Kay の講演をきいたことがある。印象に残ったのは、彼が引き合いに出した McLuhan の言葉だ。 I don't know who discovered water, but it wasn't a fish. (拙訳)誰が水を発見したかは知らないが、発見者が魚でなかったことは確かだ。 誰…

与えられた自然数リストの中に存在しない最小の自然数を求める問題。(ここでの自然数は 0 から始まる。)素朴には、以下のように実装できる。 minfree :: [Int] -> Int minfree xs = head $ [0..] \\ xs (\\) :: Eq a => [a] -> [a] -> [a] us \\ vs = filter…

これまで GHC では、スタックトレースを取ることが有効なデバッグ方法ではなかった。 なぜなら遅延評価では、(再帰であってもなくても)末尾呼び出しは単なるジャンプになるから、スタックを使わないのである。スタックに戻る場所を積むのは、case と of の中…

以下の内容は比較的どうでもいいことなので、暇な人だけ読んで下さい。Haskell では、head と tail という関数は使うなと言われる。なぜなら、引数が空リストのときにエラーを返すからである。純粋な関数は全域関数であるべきだが、head と tail は div など…

この記事の最新版は、githubで管理されています。これはHaskell Advent Calendar 2012の5日目の記事です。Haskellで作成したパッケージに対して、単体テストを書くための最新情報をお届けします。 要約 要点は4つです。 利用者に見せたい振る舞いは、doctest…

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

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

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

Haskell の クイックソート としては、以下のようなコードがよく例に出てきます。 quickSortList :: [a] -> [a] quickSortList [] = [] quickSortList (x:xs) = quickSortList lt ++ [x] ++ quickSortList gt where lt = filter (<x) xs gt = filter (>=x) xs これは、小さなリス</x)>…

Haskell で STM を使えばデッドロックがなくなる例として、食事する哲学者の問題を考えてみる。 デッドロックするコード 食事する哲学者の問題では、箸がロックの役割を果たす。Haskell の軽量スレッド間でロックを取るには、MVar を使えばよい。以下のコー…

文字列っぽいライブラリの使い方に関するメモ。後でまとめるため。コーディングの方法は、(ViewPatternを使わないとして)こんな風に変わる。ByteString も Text も IsString のインスタンスなので、OverloadedStrings を指定すると、文字列リテラルが使える…

僕の場合、/ghc-7.4.1 にインストールするので、以下のようにディレクトリを作る。 % sudo mkdir /ghc-7.4.1 % sudo chown 自分のアカウント名 /ghc-7.4.1 GHC に必要なパッケージをインストールする。64ビット環境で libgmp3-dev を入れるとはまるので、lib…