Simon Peyton-Jones - Microsoft Research
The Santa Claus Problem
The Santa Claus Problem Simon Peyton Jones, in "Beautiful Concurrency", [1] a chapter of Beautiful Code, presents the Santa Claus problem and a solution: A well-known example is the so-called Santa Claus problem, originally attributed to Trono: [2] Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves. If awakene
Philip Wadler's home page
Projects Interested in applying for a PhD or Internship? Verifying smart contracts for Blockchain Funded PhD post. (No longer available; filled by Tudor Ferariu.) From Data Types to Session Types: A Basis for Concurrency and Distribution, an EPSRC Programme Grant, joint with Simon Gay, Glasgow, and Nobuko Yoshida, Imperial. TypeScript: The Next Generation funded by a Microsoft Research PhD Scholar
Haskell Programming
Finally we see the agreement with our expectations. Iterative deepening now needs only 2MB (down from 56MB in the first try) to compute the first 100 Pythagorean triples. We may now try bigger searches. We have seen that lazy evaluation is a trade-off, which may be hurtful in some cases, in particular, in search problems over huge data structures, where it is often beneficial to recompute the resu
第9回 Haskellはなぜ遅いと思われているのか
前回は遅延評価の仕組みについて説明しました。今回は前回の知識をもとに，遅延評価の効率について検討していきたいと思います。 遅延評価のほうが速くなる場合 遅延評価の利点は，これまで何度も説明してきたように，無駄な計算を省けるところにあります。 (\x -> fst (sum x, product x)) [0..5]という式について考えてみましょう。sumとproductはいずれもPreludeの関数で，有限リストの数字を「足し合わせる関数」と「掛け合わせる関数」です（参考リンク）。この式は，先行評価ではこのように簡約されます。 先行評価 (\x -> fst (sum x, product x)) [0..5] => (\x -> fst (sum x, product x)) [0,1,2,3,4,5] => fst (sum [0,1,2,3,4,5], product [0,1,2,
Parser Combinatorというもの(その2) - 純粋関数型雑記帳
このページにはいわゆる解説記事を載せるつもりは無かったのだが、 (たいていは他にもっとうまい説明のページがあるだろうから…) どうやらこれがそうなってしまいそうである。 もっとまともな解説は http://sky.zero.ad.jp/~zaa54437/programming/clean/CleanBook/part2/Chap5.html こちらをどうぞ。(って人のページなんだけどな…) 概要 パーザコンビネータはプリミティブパーザと パーザ同士を組み合わせるコンビネータとからなる。 小さいパーザを組み立てて最終的なパーザを作り上げるのである。 パーザ パーザはいろいろなものが考えられるが、 ここでは単純に、文字列を引数にとり、 解析したもの+残りの文字列を返す関数であるとする。 type Parser a = String -> (a,String) Stringもパラメータ化すると
2004-07-30
実は昨日の話題はこれから書こうとする話とつながりがあるのだ。 (直接的には無いけど) (序) 突然であるが、Haskellは文字列処理が強力だと思う。 それも最強レベルに。 他のいわゆる文字列処理が得意であるとされる言語のように 正規表現による置換が可能であるとか、文字列がオブジェクトで 有用なメソッドがたくさん使えるとかそういった 小手先のものではなくてもっと根本的なレベルで強力なのである。 それはHaskellに於いて文字列が文字のリストであらわされていることに 起因する。わからない人から見ると文字列がリストであるということは Cにおいて文字列が配列で表されているのとかぶるかもしれない。 Haskellが文字列をリストとして持っていてうれしいというのは Haskellが全言語中でもほとんど最強のリスト操作能力を持っているからである。 Cで文字列が配列になっていても何もうれしくないのは、
d.y.d.おもしろいみろん
13:33 08/06/29 RSS of kmonos/wlog moved! http://www.kmonos.net/wlog/index.rdf いや、移動したのは15ヶ月前なので、すでにご存じの方は華麗にスルーしてください。 「ここのRSSが文字化けしてるよー」という方だけ、↑に登録変更していただけると、 直るかと思います。お手数おかけしてスミマセン。定期的に「文字化けってる」という 指摘を見かけるので再度ブロードキャストです。こう、辛辣な評議会とかで怒られそうですけど、 諸般の事情により古い方からリダイレクトかけるの難しいらしいのだよね… それはそうと、昨日の記事に追記しました。 10:26 08/06/28 Logic ∩ CS 検索してたらたまたまヒットした "On the Unusual Effectiveness of Logic in Computer Scienc
haskell.indd
46 8 2005 8 930 50 25 10 5 1 1 1 type Amount = Integer type Coin = Integer type Count = Integer -- cc :: Amount -> [Coin] -> Count cc 0 _ = 1 -- 0 1 cc _ [] = 0 -- 0 cc a ccs@(c:cs) | a < 0 = 0 -- 0 0 | otherwise = cc (a-c) ccs -- + cc a cs -- ccs@(c:cs) c:cs ccs cc.hs 1 % ghci -v0 cc.hs *Main> :set +s *Main> cc 100 [50,25,10,5,1] 292 (0.05 secs, 1264564 bytes) -v0 ghci :set +s 292 -1 cc 11 nobsun
Memoise
Memoi[sz]e、Memoi[sz]ation、メモ化の話題 メモ化ってなぁに？関数のメモ化memoise は特殊な ($) かも？Memo モジュール実装を共有する魔法 メモ化ってなぁに？ フィボナッチ関数を考えてみよう、定義は fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2) これを使って、fib 7 を計算すると fib 7 -- fib 6 -- fib 5 -- fib 4 -- fib 3 -- fib 2 -- fib 1 -- 1 | | | | | | | | | | | fib 0 -- 0 | | | | | | | | | fib 1 -- 1 | | | | | | | fib 2 -- fib 1 -- 1 | | | | | | | fib 0 -- 0 | | | | | fib 3
第1回 関数型プログラミングの世界へようこそ - 本物のプログラマはHaskellを使う：ITpro
Haskellというプログラミング言語を知っていますか？ 全く聞いたことがないという人が多いかもしれません。そういう名前の言語があるのは知っているけど，どんな言語かは知らないという人もいるかもしれませんね。でも最近では，一部の先進的なソフトウエア開発者の間で，一種のブームと言えるほど熱狂的に受け入れられています。 なぜならば，Haskellは様々な優れた特徴を持っているからです。最初に，他の言語にはあまり見られない際だった特長を一つだけ紹介してみましょう。「遅延評価（lazy evaluation，怠惰評価ともいう）」です。 遅延評価とは，与えられた値を必要になるまで評価（計算）しないということです。この性質により，不必要な計算が行われる無駄をなくすことができます。また，「潜在的に無限の大きさを持つデータ構造」といった通常のプログラミング言語では扱いの難しいものを直接扱えるため，より直接的
Haskellで速いwcを書いてみよう(1) | krの日記 | スラド
このコメントで言及されているページを見て、 Haskellのパフォーマンスチューニングというのは実際に難しいのかどうか、自分でも試してみることにしました。 お題は「Haskellで速いwcコマンドを書く」です。上記tanakh氏のページに倣い、ここで書くwcコマンドは、 いつも標準入力からのみ読む。(ファイル名の指定とかは省略) 行数、単語数、文字数を表示する。 文字はCのchar相当。(Unicodeとか複雑なことは考えない) 単語は空白区切りで数える。(punctuation等も(空白でないので)単語内の文字とする) 行数は改行文字の数を数える。(各行の最後は必ず改行で終わると仮定する) という仕様にしておきます。 なお、実行時間の測定は以下の環境で行ないました(dmesgより)。 OS:FreeBSD 6.2-STABLE CPU:Intel(R) Pentium(R) M proc
mad日記
Erlangが末尾再帰最適化をしてるか調べようとした - みずぴー日記 に興味が湧いたので，erlangのアセンブリコードを見てみた．beamのバイトコードにほぼ一対一対応していると考えていいと思う． まず単純な定義の場合 fact(0) -> 1; fact(N) -> N * fact(N-1). 以下のようになる．アセンブリコードの各行はそのままerlangのタプルとなっている．ここで， {x, N}: はx registerという．Nはレジスタ番号． {y, N}: はy registerという．レジスタという名前だが，スタック上に置かれる． {f, N}: は{label, N}に対応している．{f, 0}はプログラム終了コードのラベル． {function, fact, 1, 2}. % 引数1個, {label,2}がエントリーポイントという意味． {label,1}. {f
毎日Haskell - FSWikiLite
最終更新時間：2008年05月29日 19時15分03秒noriさんの everydayシリーズに影響されて私も「毎日Haskell」をやってみよう。基礎編はYet Another Haskell Tutorialにそってやっていくつもり。2008-05-19 【自由課題】重み順列挙を用いた幅優先探索、深さ優先探索（の思慮の足りないバージョン） （2008-05-29 追記： この回で書いているコードは無駄な動きをしている上、幅、深さとも有限な木にしか対応できていないことに気づいた。次回はこの反省に立ったネタを書くつもり）前回（2008-05-17 皿回し）使った列挙方法を幅優先探索にも使えることに気づいた。比較する値として (深さ, 選択した枝番号で構成される path) のペアを用いる。 bfs :: (a -> [a]) -> a -> [a] bfs f a = map snd $
モナドのすべて Haskell におけるモナドプログラミングの理論と実践に関する包括的ガイド
モナドのすべて Haskell におけるモナドプログラミングの理論と実践に関する包括的ガイド Version 1.1.0 このチュートリアルは、モナドの概念とその関数プログラミングにおける応用に ついて、初中級の Haskell プログラマにわかりやすく、利用価値があるような 解説をすることを旨としています。読者は Haskell になれていることを前提と しますが、モナドに関する経験は要求していません。このチュートリアルは、多 くの題材をカバーしています。後半のセクションでは、前半の題材をよく理解し ていることを前提とします。順をおって、モナドプログラミングを例示するため のサンプルコードがたくさん用意されています。一読で、すべての題材を吸収し ようというのはお勧めできません。 このチュートリアルは 3 つの部分で構成されています。最初の部分は、 関数プログラミングにおけるモナドの基本的
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Happstack - A Haskell Web Framework index.html
[Haskell] Announce: Haskell ACID Relational DBMS v0.1
Pure and simple transaction memories
[FAQ]Haskellには副作用があるのか、ないのか![[FAQ]Haskellには副作用があるのか、ないのか](https://cdn-ak-scissors.b.st-hatena.com/image/square/e8b5f753587db45b02829cec4e07adc72278f3df/height=288;version=1;width=512/https%3A%2F%2Fs.tgstc.com%2Fogp3%2Fc0d19d917305257561516bc192e7eb90-1200x630.jpeg)
http://www.tom.sfc.keio.ac.jp/~sakai/d/?date=20091106