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
The Backyard - JavaScriptのおもしろさ
JavaScript（ECMAScript）は、他のプログラミング言語の決まりに慣れ親しんでいると、非常に奇妙な存在です。一見すると、CやJavaから型宣言を省いただけの単純なプログラミング言語に見えます。しかし、prototype.jsやjQueryのような優れたライブラリのソースを眺めると、それが単なる勘違いに過ぎないことに気づくでしょう。 ここでは、prototype.jsのソースファイルを読むのに必要となるJavaScriptの文法のうち、特に重要な3点を説明します。これらは、JavaScriptでプログラムを記述するのに重要な役割を持つ反面、単にHTMLにアクセントを付ける程度の利用方法では出現しません。したがって、ここで説明するJavaScriptの「濃い」部分を知らなければ、prototype.jsのソースファイルを眺めても何が記述されているのか理解することはできないでしょう
Coqで、クイックソート - にわとり小屋でのプログラミング
（＊ 注意：今回はCoq 8.1以上を使用。 ＊） 今回は、らくがきえんじんで、昔 言及されていた、クイックソートに挑戦してみる。 Coqで、再帰する関数を書く場合は、Definitionコマンドではなく、Fixpointコマンドを使う。 しかし、Fixpointによる関数定義では、明らかに停止する構造を持つ必要がある。 Coqでは、必ず停止する関数のみが定義できる、という制限のため、このように再帰する関数を定義するのは難しいが、Coqで作った関数は、必ず停止して結果を返す、という性質を保っている。 しかし、Fixpointによる定義では、簡単に定義できない再帰関数もある。 例えば、次のように、クイックソートの関数を素直にかいてみると、以下のようなエラーになる。 (* クイックソートの定義 失敗例 *) Fixpoint qsort (l : list A) : list A := mat
d.y.d. memo: POPL 2
17:17 08/01/30 ところで C++ か JavaScript か PHP が批判されてるのを見ると思わず何か言いたくなってしまうのだけど、 考えてみるに、他の言語だと割とどうでもいい。そういう意味では、今の自分が好きなプログラミング言語は この３つということになるのかなあ……などと徒然なるままに思いました。 単純に、つきあいが長い方から３つというだけかもしれない。 いやしかし、PHPに対する批判の多くはその通りであるとは思うのですが。 Attacking PHP で触れられてる「リストであり辞書でもある」 array ってあれは普通に便利じゃないです？ 結構他の言語でも欲しくなるのですが。 17:08 08/01/29 PHP で Yコンビネータ PHP じゃ Y コンビネータつくれない と聞いて。 <?php // PHPでは関数呼び出しは 関数名(...) か 変数(...
SAT ソルバで数独を解く方法 - まめめも
数独は非常に SAT に変換しやすい問題です。全部参考文献 *1 に載っている内容ですが、なるべくわかりやすく説明してみます。ちょっと長いです。 SAT とは まず SAT をごく簡単に説明します。すでに SAT を知っている人はここは読み飛ばしてください。 命題論理式の形の一つに乗法標準形のというのがあります。変数か変数の否定 (リテラルと言います) を or だけでつないだ式 (節と言います) を and だけでつないだ論理式のことを言います。つまり以下みたいな形です。 ( a1 or !a2 or ... or an) and ( b1 or !b2 or ... or !bn) and ... and (!z1 or z2 or ... or !zn)SAT は「a1 や zn などの変数にうまく true か false を代入して、上の式全体を true にできるか」という問題
第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
テンプレートメタプログラミング - Wikipedia
出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。 記事の信頼性向上にご協力をお願いいたします。（2022年9月） テンプレートメタプログラミング（英: template metaprogramming）は、メタプログラミング技法の一種であり、コンパイラがテンプレートを使って一時的ソースコードを生成し、それを他のソースコードと結合してコンパイルする方式である。テンプレートが出力するものは、コンパイル時の定数、データ構造、関数定義などがある。テンプレートの利用は言わばコンパイル時の実行である。この技法は様々な言語で使われている（C++、D言語、Eiffel、Haskell、ML、XLなど）。 メタプログラミング手法としてのテンプレート利用には2段階の操作が必要である。まずテンプレートを定義し、次にそれをインスタンス化しなければならない。テンプレートは生成す
思いて学ばざれば則ち殆うし - sumiiのブログ
あるところに同じようなことを（ほとんど成り行きで）書いたのですが、重要な問題のような気がしてきたので、こっちにも書いてみる。 一般に、関数型言語やプログラミング言語（および計算機科学、ないし任意の専門）についての情報は、 一般書・一般誌、Webやメーリングリストやブログ 教科書・専門書 論文 口頭での議論（学会発表や質疑応答、グループのミーティング、部屋での会話） などで交換されます。 で、一般に情報の「ディープさ」は上から下へ行くほど濃くなると思うのです（少なくとも僕の専門分野ではそう）。そのごく一部である1.だけ（しかも日本語onlyで）「勉強」していろいろと議論するのは、（何もしないよりは良いのかもしれませんが）非常に危険です。その危険をちゃんと意識していればno problemですが。「高速道路」の話と同じことかも。 たとえば、日本のネット(?)では今になって妙に持ち上げられている
ひげぽん OSとか作っちゃうかMona- - 「計算機プログラムの構造と解釈(SICP)」を読み終えて
約半年をかけて計算機プログラムの構造と解釈(SICP)を読み終わりました。 （途中で、練習問題をスキップしたりしましたが・・・） 半年もかけたのでちょっとだけ振り返って見ます。 SICPを読む過程で得たもの まずはSICPを読む過程で得たものからざっと列挙してみよう。 構文解析を理解し自前で実装できるようになった 字句解析を理解し自前で実装できるようになった ストリームを理解した 遅延評価を理解した 手続きが first class objectである言語での考え方を学んだ 型変換の導入の動機とその意味を理解した 手続きの抽象化の導入の動機と過程を学んだ 高階関数を使ったり書けるようになったりした クロージャを理解した Schemeを書けるようになった 再帰処理を自然に書けるようになった フルスクラッチでインタプリタを書けるようになった コンパイラを自前で書くことが出来そうだとの感触を得た
「計算機プログラムの構造と解釈(SICP)」を読み終えて by なつたん - なつたん
ひげぽんさんの所をパクってテンプレートにして書いてみました。 練習問題をスキップしつつ、私も約半年でで読み終えました。とても楽しい日々を過ごすことができました。 SICPを読む過程で得たもの ・遅延評価とstream ・制約プログラミング、ロジックプログラミング、amb ・Emacs(Meadow)＋gauche＋Quackの組み合わせ便利 ・同じ事を表現するのに、抽象度を上げたり、下げたりできること。 ・手加減してあればLispのソースも追えるようになった。手加減していないのは駄目。 ・Lisp特有の、手続きを評価する→S式ができる→また評価する→S式ができる、という気持ち悪い再帰の存在。 ・SICP読み仲間ではないけどいろんなblogつながり。組み込みとFPGAだけでない、いろんな世界がある事をあらためて感じた。 SICPを読みはじめたときの動機を振り返る ・関数型言語について Lis
後方参照のある正規表現の能力 - まめめも
定期的に出てくる話題ですが、プログラミングで出てくる正規表現は正規表現ではないので、素数判定ができます。正確には、文字列の長さが素数かどうかを判定できます。2 文字以上のマッチが 2 回以上出現するかどうかを見ます。後方参照がポイント。 p (2..30).select{|x| !("X" * x)[/^(..+)\1+$/] } #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] ところで、{ a^n | n は素数 } は文脈依存言語のはずなので、後方参照のある正規表現は線形拘束オートマトン以上の表現力を持つことになるのでしょうか。でも、文脈自由文法である { a^nb^n | n は自然数 } や括弧の対応は書けなさそうです。ちょっと調べてみても、後方参照のある正規表現の能力はよくわかりませんでした。 とりあえずPerl の正規表現マッチングで 3-CN
毎日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 つの部分で構成されています。最初の部分は、 関数プログラミングにおけるモナドの基本的
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
OCaml - The OCaml Manual
ICS | Utrecht University
初心者が書いた OCaml 入門
Route 477
数理科学的バグ撲滅方法論のすすめ---目次 | 日経 xTECH（クロステック）
