Haskell のリストはモナドであり、それは非決定性の文脈を表すと言われます。しかし、そのことを扱った例題は少なくて、しかもイマイチでした。そこで、Scheme で書かれたよい例題を Haskell で書き直してみました。 「On Lisp」の「非決定性」の章では、謎めいた関数 choose と fail が出てきます。こんな難しい話をしなくても、Haskell では単に全探索することで非決定性を実現できます。なぜなら、Haskell の評価戦略は遅延評価なので、答えの先頭しか要求しなければ、残りの答えは探さないからです。 というわけで、Haskell で非決定性の問題を解くことは、リストを使って普通にプログラミングすることとなんら変わりません。 三平方の定理 「もうひとつの Scheme 入門」に載っている三平方の定理に関する問題を解いてみましょう。 x = [1,2,3,4,5],

Haskell の優雅さを示すためによく使われるコードは、優雅さと分かりやすさだけに特化しており、現実的には遅いことが多い。書き手は他に効率のよい実装があることを知っているのだけれど、読み手はそうではないから、後で効率が悪いと気づいて愕然とするみたいだ。 この記事では、神話になっている例を3つ取り上げ、効率のよい実装と合わせて紹介する。その 3 つの例とは、以下の通り。 フィボナッチ数 素数生成 ソート フィボナッチ数 遅延評価を活かした優雅なフィボナッチ数の実装は、以下の通り。 fib n = fibs !! n fibs = 0 : 1 : zipWith (+) fibs (tail fibs) Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」はとても遅いにも書かれているように、この実装は遅い。 その理由は、(+) の計算が遅延し、その待機

端的に説明するなら「正しく型付けされた項はおかしくなることがない」ことを学ぶための壮大な本。型に関する圧倒的な知識を持ち、説明がうまく、根気づよい人にのみ記すことができた英語の良書が、型システムを愛する訳者と監訳者、および(書中に名前が出てくる方も含む)豪華なレビュアの情熱によって翻訳された記念すべき書籍。税抜きで6,800円と高いが、それ以上の価値がある本である。 型システム入門 −プログラミング言語と型の理論− 作者: Benjamin C. Pierce,住井英二郎,遠藤侑介,酒井政裕,今井敬吾,黒木裕介,今井宜洋,才川隆文,今井健男出版社/メーカー: オーム社発売日: 2013/03/26メディア: 単行本（ソフトカバー） クリック: 68回この商品を含むブログ (11件) を見る 動的言語のプログラマと静的型付き言語のプログラマの間で、型についての議論が定期的に沸き上がる。今後、

Haskell(GHC)での軽量ユーザスレッドの実装方法で、Cmm が軽量スレッドのポイントと書きました。しかし、GHC の実装者 Simon Marlow 先生から「Cmm は関係ないよ」と教えて頂きました。 StgCall StgCall がいくつかのレジスタを保存するのは、採用しているCの関数呼び出し規約がそうなっているから。スレッドとはまったく無関係。 GHC のランタイムは C で書かれている。よって、スケジューラからスレッドを呼び出すと、C から Haskell を呼び出すことになる。C では、呼び出された関数がレジスタを保存しなければならない。Haskell の関数には、こういった制約はない。なので、C から Haskell の関数を呼び出す際は、C の規約を肩代わりしてやる必要がある。それが StgCall。 スタック Haskell のスタックは C のスタックと同様、特

最近、スタートHaskellで「カリー化された関数のメリットは何か？」という質問が出た。そのすぐ後に、kmizuさんがカリー化の誤用に対して警鐘を鳴らしてしていた。僕からするとkmizuさんの「カリー化の定義」も誤用に思えたので、調べるとともに考えたことのまとめ。 いろんな定義 「カリー化する」という用語は、すくなくとも以下の3つの意味で使われているようだ。 部分適用という意味 これは明らかに間違い 「複数の引数を取る関数」を「一引数を取る関数のチェインに直す」こと これはkmizuさんの定義。世間でもよく使われる。 「構造体を一つ取る関数」を「構造体のメンバーを複数の引数にばらし、一引数を取る関数のチェインに直す」こと これは僕の定義。というか、Haskellコミュニティの定義。 「部分適用」の意味で使うのは明らかに間違いのなで排除。定義2と3について議論する。あとで、部分適用とは何かに

状態をモナドで実現する方法を考えます。 リスト 例は簡単な方がいいので、データ構造として Lisp 風のリストを定義しましょう。 data List a = Nil | Cons a (List a) deriving Show リストは、こんな風に表せます。 Cons "c" (Cons "b" (Cons "a" Nil)) Lisp 風の cons も定義してみましょう。 cons :: a -> List a -> List a cons x xs = Cons x xs cons "c" $ cons "b" $ cons "a" Nil → Cons "c" (Cons "b" (Cons "a" Nil)) 状態を持つリスト さて、この Lisp 風のリストに、要素の数を覚えさせておきたいとしましょう。もちろん、数えれば分りますが、数えなくても一瞬で分るようにしたいのです。

早いもので、今年も12月25日となりました。メリークリスマス！ うちのちびっ子怪獣たちも、サンタさんに書いた手紙通り、レゴをもらってご満悦のようです。 そして今日は、Haskell Advent Calendar 2013 の最終日でもあります。 Haskellらしい？ 「純粋なコードで構成するのが Haskell らしいプログラムであり、IOはHaskellらしくない」という発言をよく耳にします。 確かに、命令プログラミングの世界から関数プログラミングの世界にやってきたとしたら、 不変データを使った永続データプログラミング 部品プログラミング 純粋なコードに対する性質テスト などには、衝撃を受けることでしょう。 でも、純粋なコードは、Haskell の世界の半分でしかありません。そこは、コンパイラーという保護者に守られた未成年の世界です。Simon Peyton Jones さんの言葉を

関数型言語での関数について、Haskell を用いて説明します。 関数の型 関数の型は、-> を使って書きます。例えば、Int を Char に変換する chr という関数の型は、以下のようになります。 chr :: Int -> Char 一引数の関数の型は、まぁこんなもんだと思えるでしょう。びっくりするのは、引数が増えたときです。たとえば、replicate という関数の型を見てみましょう。 replicate :: Int -> a -> [a] replicate は、第二引数で指定されたデータを第ー引数に指定された個数分用意して、リストにして返す関数です。([] は配列ではなく、リストです。) 次のように動きます。 > replicate 3 "foo" → ["foo","foo","foo"] a は型変数といって、任意の型を取れます。なじめない人は、具体的な型を当てはめてみ

僕が Haskell を学び始めた頃、Haskell の文法はすんなりとは頭に入ってきませんでした。もともと僕はプログラミング言語の学習能力が低いので、僕だけかもしれませんが、「はじめからこう言ってもらえれば分かったのにぃ」ということを書きます。 はじめの一歩 分岐は case で書きます。以下に Maybe a に対する例を書きます。 case mx of Just x -> ... Nothing -> ... 念のため、Maybe a の定義も見てみましょう。 data Maybe a = Nothing | Just a 列挙されているデータ構成子を case に列挙できることが分かるでしょう。このように、case でマッチできるのは、データ構成子で表現されたパターンになります。 ワイルドカード たとえば、以下のような型を定義したとします。 data Foo = A | B | C

誤訳 以前、「サーバサイドJavaScriptのNode.js、最初はCやHaskellを検討し失敗。開発者ライアン・ダール氏へのインタビュー」という記事が twitter で話題になっていました。 ―― なぜJavaScriptを選んだのでしょう？ ダール氏　実は最初は違いました。最初はC、Lua、Haskellなどで失敗していました。そんなときV8（Chromeが採用しているJavaScriptエンジン）に気がついて、やろうとしていることに対してJavaScriptが完璧な言語だと突然ひらめいたのです。 ただでさえ、Haskell は遅いと誤解されているのに、このような悪意さえ感じらえる訳だと、さらに誤解が深まりそうです。原文にはこう書かれています。 Dahl: Originally I didn’t. I had several failed private projects doi

岡山大学で、関数プログラミングの講義を一コマ担当しました。資料は、函数プログラミングの集いで使った関数プログラミングの道しるべを流用しました。ちゃんと用意しなくて、講義を受けた学生には申し訳ないです。 講義内容に関して質問を頂きました。同じような疑問を持つ人も多いと思いますので、担当教官の許可を得てここに公開します。 永続データプログラミングの意義は分かったが，破壊しないと効率が悪いのではないですか．配列のような構造が世の中には多い気がします．メモリは足りなくなりませんか． 基本的に永続と呼ばれているデータは、共有の効率が高く、しかも不要になった部分はすぐに GC に回収されます。また、GHC の GC はすごく優秀であることが知られています。 Haskell では、下位のレイヤーではデータを破壊できて、たとえば固定長のバッファーを使い回すといったことも可能です。ただ、それは普通のプログラ

Perl6 は何年経っても正式にリリースされません。そんな Perl6 を Audrey Tang さんは、たったの数ヶ月で作りました。その実装は Pugs と呼ばれています。短期間の開発を可能にした秘密兵器は Haskell です。 その Audrey さんが、2006年に日本で Haskell について説明してくれました(資料)。残念ながら、そのころの僕は Haskell に興味がなかったのでチュートリアルは受けていませんが、その概要にはこう書かれています。 コーナーケースを探すのにユニットテストを書くのに疲れた？ QuickCheck を使ってコンピュータに書かせちゃいましょう。正規表現ベースのパーサはメンテナンスしにくいのに気づいた？ Parsec を使って 15分で Perl6 の完全なパーサを書く方法を勉強しましょう。デッドロックやレースコンディションはもううんざり？ STM

この記事の目的は、Applicative 信者による Applicative スタイルの布教です。 簡潔に結論を述べると、 foo = do a <- m1 b <- m2 return (f a b) のようなコードを書きたくなったら foo = f <$> m1 <*> m2 と書きましょうということ。 合い言葉は、「do と return をなくせ！」です。 FunctorとMonadの間 Functor を特殊化した型クラスがMonadで、Monadの方が強力です。なぜなら、メソッドが増えるからです。 Functorのメソッドはfmapです。fmapの別名を (<$>) といいます。(この記事では、(<$>) と liftM を同一視します。) そして、Monadのメソッドは、ご存知の通り (>>=) と return です。 FunctorとMonadの間にApplicative

構造化定理によれば、分岐、反復、逐次があれば、すべてのロジックは記述できます。分岐については、Haskellの文法(分岐編)で説明しました。今日は反復について説明します。逐次に関しては、少し難しい内容ですが、QAで学ぶMonadを読んで下さい。 for 文 多くの言語では、素朴な繰り返しを実現するためには for 文や while 文を使います。for文を単純に数え上げとして使う場合、カウンターである変数 i が再代入できるとことが前提になっています。 Haskell では、変数に再代入はできません。それは、for 文がないことを意味します。どうやって、繰り返しを実現するのでしょうか？ その答えは、再帰です。 対比するための言語として JavaScript を用いることにします。まず、以下のように渡された整数の配列の要素をすべて足し合わせるプログラムを考えて下さい。 function su

The Typeclassopediaには、以下のような文章があります。 結局、あらゆる誇大広告にもかかわらず、Monadは単なる型クラスに過ぎません。 また、The Trivial Monadでは、以下のように述べられています。 Haskell の Monad は型クラスの1つです。Haskell の型クラスは、複数の型で共通する API を定めます。だから、Monad という型クラスとは、型の集合に対する共通の API です。 共通の API とは、return と (>>=) のことです。 こう言われると、すぐに「その共通のAPIを使うと何が嬉しいの？」という疑問が湧くでしょう。もちろん、共通の API を使う嬉しさは、後から型を変えたときに、実装を変えなくてもいいことです。この記事では、その一例をお見せしましょう。 私が「Monad で実装してよかった」と感じたことがあるのはパーサ

この記事は、Monad でつまづいた Haskeller のための Monad 再入門です。 Monadとは何ですか？ Monad とは、単なる型クラスの一つです。難しいという風評もありますが、それ以上でもそれ以下でもありません。 この型クラスのメソッドは、return と >>= です。 class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a つまり、以下を満たす型の集合が Monad です。 m a で表現できるように一つの型変数を格納するコンテナ型 >>= と return を実装 return は新しいコンテナを作り、>>= は二つのコンテナを合成します。 Monad のインスタンスは失敗系と状態系に大別できます。以下に代表的なインスタンスを示します。 失敗系: Maybe、[] (リスト)

まずは、Audrey さんが言った Haskell の殺し文句を思い出して頂きたい。 正規表現ベースのパーサはメンテナンスしにくいのに気づいた？ Parsec を使って 15分で Perl6 の完全なパーサを書く方法を勉強しましょう。 15分というのは誇張が入っていると思うが、正規表現が保守しにくく、Haskell の Parsec は強力で保守し易いのは事実だ。その理由を Perl と Haskell のコードを示しながら説明してみたいと思う。 Perl を愛する方に：この記事は Perl を攻撃するために書いたのではない。Perl を選んだのは、正規表現を広めた言語であり、僕がそれなりに Perl のコードを書けるためである。この記事の目的は、正規表現よりも関数型パーサー(Parsec)の方が優れていると示すことだ。 例題 この記事では例題として、IPv4 アドレスを解析する関数を書く

これは HTTP/2 アドベントカレンダー19日目の記事です。 この記事はたくさんの資料を読んだ上で書きましたが、間違いとか勘違いとかがあるかもしれません。もしあれば、指摘していただけると幸いです。 実質的に必須となったTLS HTTP/2は、HTTP/1.1と同じく、暗号化なし/ありのポートとして、80と443を使います。そのため、通信開始時にHTTP/1.1とHTTP/2をネゴシエーションするための仕組みが、HTTP/2で定められています。 このように仕様としては暗号化なしのHTTP/2が定義されていますが、Firefox や Chrome が TLS を要求するために、実質的は暗号化ありが必須となっています。これは、米国の監視プログラムPRISMに代表される広域監視(pervasive surveillance)に対抗するために、IETFがさまざまな通信にプライバシの強化を要求する方

この記事は、Haskellを勉強してある程度分かったけど、Monadで挫折した人のための記事です。10分間で、Monadに対する納得感を得ることを目的としています。他の言語でいう「モナド」にも通用する内容ですが、Haskell の文法や用語を用いますので、他の言語の利用者に分かるかは不明です。 Haskellを勉強したのですから、 代数データ型 型クラス は分かっていることにします。Monad は、単なる型クラスの一つで、それ以上でもそれ以下でもありませんから、この二つが分かってないと話になりません。 また、言語内DSL(以下、DSLと略記)という考え方を知っていることも仮定します。Monad とは、DSLのフレームワークという直感を与えるのが、この記事の主眼ですからね。 さらに、構造化定理をいう単語を聞いてもビビらない人を想定しています。逐次、反復、分岐があれば、計算しうる計算はすべて記