このスライドはブログ記事として書き直しました。このスライドよりブログ記事の方がわかりやすいと思います。 http://d.hatena.ne.jp/syamino/20120524/p1

This site serves to collect and disseminate research, resources, and tools for the investigation of homotopy type theory, and hosts a blog for those involved in its study. Homotopy Type Theory refers to a new field of study relating Martin-Löf’s system of intensional, constructive type theory with abstract homotopy theory.  Propositional equality is interpreted as homotopy and type isomorphism as

ラムダ計算でEither Either型の値をパターンマッチする状況を考えます。 「データコンストラクタのパターンマッチ」は，下図のようにしてラムダ計算で表現できます。 ラムダ計算でBool 今度は，Bool型の値をパターンマッチする状況を考えます。 TrueやFalseには引数が無いので，(3)や(4)はλで囲みません。 パターンマッチ = 「データコンストラクタを他の関数に置き換えること」 パターンマッチによって，Leftがlに置き換わります。以下同様です。 「データコンストラクタを置き換える」という概念について，もう少し詳しく考えていきます。 データコンストラクタの置き換え方は2種類ある リストのような再帰的なデータ型では，データコンストラクタの置き換え方が2種類あります。 data List a = Cons a (List a) | Nil (1) 全てのデータコンストラクタを置

村主です。 ２０１１年９月２１日に、ICFP2011で来日していたSimon Peyton-Jones先生を弊社にお招きして、Glasgow Haskell Compilerの最新事情について講演をしていただきました。当日は体が浮きそうなほどの風が吹く大嵐でしたが、多くの人の協力のおかげで無事に終えることができ、感謝しています。 サイモン先生からスライドを分けてもらったので、講演会の動画とあわせて読む形で、記事にまとめてみました。Haskell/GHCのさまざまなトピックをカバーするこの講演、みなさんのHaskell勉強の一助となれば幸いです。 サイモン先生に「君たちも何か話してよ」と頼まれたので、僕が流体計算言語Paraiso(リンク先にスライドあり)の話をまずしています。 31:46 頃からサイモン先生のトークが始まります。まずはHaskell Communities and Acti

この記事は、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、[] (リスト)

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

バレンタインチョコ欲しい！ 田中です。 Iterateeの素晴らしいチュートリアルを見つけたので、今回はその翻訳をお届けしようと思います。以前、The Monad Reader Issue 16 のiterateeの記事をベースにした解説記事を書いたのですが、こちらの記事はかなり概念的なところから始まり、結構天下り的にiterateeの定義を受け入れていたのに対して、こちらの記事は、一貫して具体例からの抽象化で話が進み、また易しく書かれているので、比較的理解しやすいと思います。また、実際の実装に即して解説されていますので、読み終えて即実際に使ってみることが出来るでしょう。 このチュートリアルを書かれたMichael Snoymanという方は、現在YesodというHaskellのWebフレームワークを精力的に開発されています。Yesodには実際にiterateeがふんだんに用いられており、そ

今日はProofCafeでCPDTの三章を読み進めたが、そこでCoqではInductive型のコンストラクタの引数が関数のとき、その関数の左側に自分自身が現れてはいけないということを学んだ。もしそれを可能にしてしまうと無限ループが定義でき、公理系が矛盾してしまうからだ。次のシンプルな例を見てみよう。 Inductive t (A: Set) : Set := | T : (t A -> A) -> t A. 一見なんの問題も無さそうな この型定義は失敗し、次のようなコンパイルエラーが出力される。 Error: Non strictly positive occurrence of "t" in "(t A -> A) -> t A".もしこの型が定義できたとすると次のような関数が定義できてしまう。 Definition ワォ (T f) := f (T f). ここで (ワォ (T ワォ)

OCaml では，let rec を使わずに再帰関数を模倣することができる． 但し「for ループを使えばできる」とかそういう話ではない． 例えば，階乗を計算する関数 fact は，通常 let rec を用いて， let rec fact n = if n > 0 then n * fact (n-1) else 1 と再帰的に定義されるが，次のように let rec を使わなくても定義できる．let turing (`M x) y = y (fun z -> x (`M x) y z) let fact = turing (`M turing) (fun f n -> if n > 0 then n * f (n-1) else 1) ちょっと読み難いが，実際に fact 10 と実行してみれば， 3628800 と正しい出力が得られることが確認できるだろう． このカラクリを支えている