型理論 なんて自分には関係ないと思っているあなたへ
24. ...... Lemma reduce_lemma : forall ctx (ctx' : seq (term * typ)) t ty, typing ([seq Some p.2 | p <- ctx'] ++ ctx) t ty -> Forall (fun p => reducible ctx p.1 p.2) ctx' -> reducible ctx (substitute_seq 0 [seq p.1 | p <- ctx'] t) ty. Proof. move => ctx ctx' t ty; elim: t ty ctx ctx'. - move => /= n ty ctx ctx'. rewrite /substitute_seqv typvar_seqindex subn0 size_map shiftzero. elim: ctx' n => [|
モナドはメタファーではない · eed3si9n
2011-05-28 Scala界の関数型プログラミング一派を代表する論客の一人、@djspiewak が 2010年に書いた “Monads Are Not Metaphors” を翻訳しました。翻訳の公開は本人より許諾済みです。翻訳の間違い等があれば遠慮なくご指摘ください。 2010年12月27日 Daniel Spiewak 著 2011年5月29日 e.e d3si9n 訳 僕は今、約束を破るところだ。およそ三年前、僕は絶対にモナドの記事だけは書かないと自分に約束した。既にモナドに関する記事は有り余っている。記事の数が多すぎてその多さだけで多くの人は混乱している。しかも全員がモナドに対して異なる扱い方をしているため、モナドの概念を初めて学ぼうとする者は、ブリトー、宇宙服、象、砂漠のベドウィン (訳注: アラブ系遊牧民) の共通項を探す努力をするハメになっている。 僕は、この混乱した
ArrowによるHaskellプログラミングの基礎。…パイプ感覚で順次/分岐/繰返し - よくわかりません
Programming with Arrowsを読んで理解したつもりのメモ。誤りなど乞うご指摘。 （復習）Arrowってなに？ と思って以前調べたメモが"3分で解るHaskellのArrowの基本メモ - よくわかりません"。それにちょっと補足というか観点を変えてまず感覚の整理。 Monadに色んな種類があるように、Arrowも色んな種類がある。 Monad: IO、Maybe、… Arrow: 関数そのまんま(->)、Kleisli m、… ある種類のMonadに色んな型の色んな値を入れられるように、ある種類のArrowに色んな型の色んな関数を入れられる。 Monad: Maybeの例→ 「Maybe Int」 にreturn 0もreturn 777もＯＫ。「Maybe Char」 にreturn 'a'もreturn ' 'もＯＫ。 Arrow: (->)の例→ 「Int -> In
第14回 型＝命題，プログラム＝証明
MLの型と型推論 この連載でも何回か触れたが，MLやHaskellなど多くの静的型付き関数型言語には，「型推論」という機能がある。これは，プログラム中の変数や関数の型を省略しても，「もっとも一般的」な型を言語処理系が勝手に推論してくれる，という機能だ。 例えば，次のように，二つの引数xとyを受け取って，(x, y)という組を返す関数pairを定義してみよう。 > ocaml Objective Caml version 3.10.0 # let pair = fun x y -> (x, y) ;; val pair : 'a -> 'b -> 'a * 'b = <fun> # このように，pairは「何らかの型'aを持つ値と，何らかの型'bを持つ値を受け取り，'a型の値と'b型の値の組を返す」と推論される。一般に，t1 -> t2は，型t1の値を受け取って，型t2の値を返す関数の型であ
Programming in Haskell
Programming in Haskell ページへようこそ このサイトについて このサイトは、Haskell でプログラミングを楽しむためのサイトです。 現在のところ、WiLiKi というWiKiシステムで運用されています。WiLiKiの使い方は、 WiLiKi:WiLiKi:リファレンスマニュアルを参照してください。 メイリングリスト 「Haskellプログラミングを楽しむための」メーリングリストがあります． MailingListのページをご覧ください． チャット 「Haskellプログラミングを楽しむための」チャット・ルームがいくつか存在します． ChatRoomのページをご覧ください． サイトマップ Introduction Haskell とは Definition 仕様と標準ライブラリ Tutorial チュートリアル やさしいHaskell入門 モナドのすべて なぜ関数プ
本物のプログラマはHaskellを使う：ITpro
筆者 shelarcy Haskellは，関数型プログラミングというジャンルに属する言語です。Haskellや関数型プログラミングを題材に物事を見ていくことで，今まで思いもよらなかったような未知の世界を知ることができるでしょう。 プログラミング言語を学ぶという行為には， 言語の基本的な文法や考え方を理解する 言語の文化圏で広く使われている考え方に親しんでその言語らしい書き方を習得する 単に言語を使ってできること以上の知恵を学ぶ の3段階があります。この連載では，三つ目の段階を目標に，Haskellプログラミングの世界を一つひとつ丁寧に紹介していきます。 更新は毎月第1水曜日（1月のみ第2水曜日）
モナドで悟りをひらきたいのなら - 図でわかる(?)モナド - Pixel Pedals of Tomakomai
圏論の最大の武器はダイアグラムなので、モナドで悟りをひらきたいのならダイアグラムを使えばいいんじゃないでしょうか。 ダイアグラムの書き方 例えば、「 f :: a -> b 」とか「length :: [a] -> Int」は以下のように書きます。型を点で、関数を矢印で書きます。 ダイアグラムの利点は、fやlengthの中身を忘れて簡略化することができることです。人間の脳ができることには限りがあるので、注目する情報が少ない方が理解しやすくなるってスンポーです。 なお、 合成 g . f は図示する時に順が逆になるので気をつけて下さい。これは、合成関数の適用が g ( f x ) と書けることに由来してます。まずfを適用し、次にgを適用するということです。 return と >>= の図示 今回のダイアグラムの約束として、元となる型(Bool, Char, Int 等)は最下段に書きます。そ
第14回 関数脳のつくり方 Second Season 〜モナドで悟りをひらく〜 - 刺激を求める技術者に捧げるScala講座：ITpro へのツッコミ - kmizuの日記
ITProのScala連載「刺激を求める技術者に捧げるScala講座」の第14回 関数脳のつくり方 Second Season 〜モナドで悟りをひらく〜がはてなブックマークで150ブクマ超えるなど注目を集めていますが、読んで見ると初学者に誤解を与える箇所が散見されるので、一応、連載に関わってる者(といっても１回記事書いただけですが)の一人としてツッコミを入れさせていただきます。 「参照透明性を保持しながら手続き型的な記述をするための枠組み」？(p.1) モナドとは，関数型言語で，参照透明性を保持しながら手続き型的な記述をするための枠組みです。 早速ですが、これは、IOモナドやStateモナドには当てはまっても、全てのモナドについて当てはまるものではないですよね。たとえば、Maybeモナドではこれは当てはまりません。 「モナドがHaskellで必要な理由」？ これはページタイトルの一部ですが
第14回 関数脳のつくり方 Second Season ～モナドで悟りをひらく～
大手SIベンダにてSEやPMやアーキテクトとして勤務したのち，株式会社豆蔵を経て，現在は合同会社シンプルアーキテクト代表社員であり，株式会社匠Business Placeのチーフコンサルタント。主に超上流のプロセスである要求開発やオブジェクト指向，アジャイル開発のコンサルタントとして活躍中。開発の現場にこだわり，開発の現場を少しでもよくしたいと日夜奮闘している。要求開発アライアンス執行委員。著書に『オブジェクト脳のつくり方』や『eXtreme Programming実践レポート』（ともに翔泳社発行。後者は共著）などがある。 Javaなど，オブジェクト指向や手続き型のプログラミングの経験はあるけれど，関数型のプログラミングは初めてという皆様のための，そして筆者自身のための「関数脳のつくり方」シリーズのSecond Season（First Seasonはこちら）。今回は「モナド」を取り上げま
ラムダ計算基礎文法最速マスター - 貳佰伍拾陸夜日記
ラムダ計算は, 多くのプログラミング言語, とくに関数型言語の原形になっています. ラムダ計算について理解しておくことは, 多くのプログラミング言語の習得に役立つでしょう. ラムダ計算はチューリング完全で, 計算能力としてはふつうのプログラミング言語と同じです. ラムダ計算で計算を書く訓練をしておくことは, 任意の計算を関数のみを使って(他の制御構文を用いずに)書くときに役立ちます. ふつうに書いたら煩雑な処理を, 関数型言語のやり方で書くとすっきりすることが多々あり, コードを自由自在に書くためには必須の考え方と言えるでしょう. 項 ラムダ計算の式を項(term)と言います. 項は変数, 抽象, 適用のいずれかです. 変数 変数(variable)はふつう1文字で書きます. 変数には関数内の束縛変数(bound variable)か自由変数(free variable)かという区別があり
Y コンビネータって何？ - IT戦記
このエントリの 親友へ。ブログを書こう。 - IT戦記 y がブログを始めたみたいなので、読んでみた。 で、最新のエントリを読んでみたら、 Y コンビネータというものについて書いてあったので、 Y Combinatorが凄すぎる！ - yuji1982の日記 Y コンビネータって何ってところから、自分でもいろいろ考えてみた。 結局なんなのかさっぱり分からなかったんですが、自分が考えたことをまとめておく まず、フィボナッチ数を求める fib を定義する var fib = function(n){ return (n <= 2) ? 1 : (arguments.callee(n-1) + arguments.callee(n-2)); }; fib(10); おお！ JS すげー！名前は n しか使ってねーよ！ めでたし、めでたし。。。。じゃなくて！ JS が素晴らし過ぎて話が終わってしま
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
なぜ関数プログラミングは重要か
John Hughes, Institutionen för Datavetenskap, Chalmers Tekniska Högskola, 41296 Göteborg, SWEDEN. rjmh@cs.chalmers.se この日本語訳は原著者の承諾を得て山下がここに公開するものです。 この訳文についての、御指摘などは山下伸夫(nobsun .at. sampou.org)までおねがい いたします。 翻訳最終更新日 : 2011-09-17 原文 "Why Functional Programming Matters" 日本語訳PostScript この論文は1984年以来何年ものあいだChalmers大学のメモとして回覧された。 1989年と1990年に幾分か改訂をしたのが[Hug89]と [Hug90]である。この版はもとのChalmer大学のメモ のnroff原稿をもとに
ゲームプログラミング界の巨人、Tim Sweeneyが「未来のゲーム開発テクノロジー」を語る
ゲームプログラミング界の巨人、Tim Sweeneyが「未来のゲーム開発テクノロジー」を語る 超並列処理、次世代のゲームグラフィックスはソフトウェアレンダリングに回帰する 9月9日～11日開催 会場：昭和女子大学 「CEDEC 2008」の最終日、海外トラックの目玉となるセッションが開催された。講演者は米Epic GamesのCEO、Tim Sweeney氏。Sweeney氏はEpic Gamesの創設者であると同時に、1997年にリリースされたFPS「Unreal」のメイン開発者であり、また現在では同社の技術ディレクターを兼任して研究開発を続けているという現役の最先端テクノロジストだ。 「未来のゲーム開発テクノロジー」と題されたこの講演では、Sweeney氏が予測するゲーム開発の将来像が提示された。Sweeney氏は評論家やアナリストではなく、その将来像を具現化する最前線に立っている人物
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
転送中
Amazon.co.jp: 関数プログラミングの楽しみ: 山下伸夫 (翻訳), ＪｅｒｅｍｙＧｉｂｂｏｎｓａｎｄＯｅｇｅｄｅＭｏｏｒ (編集): 本
数理科学的バグ撲滅方法論のすすめ---目次 | 日経 xTECH（クロステック）