Haskell

Type-level Quine (未完)

「型システム入門」(TAPL 日本語版)の発売を記念して、型にまつわる何かを書こうと思い、とりあえず型レベルプログラミングでの Quine に挑戦して見ました。 TAPL の内容には全く関係ありません。型クラスは発展的なものなので、入門書である TAPL には名…

quine リレー

Update (2013-07-15): I improved this program to 50-language version. 50 言語版にパワーアップさせました。 これはこのプログラム自身を出力する Unlambda プログラム、を出力する Whitespace プログラム、を出力する brainfuck プログラム、を出力する …

Re: ブロックソートを Haskell で書いてみた

ref: http://d.hatena.ne.jp/mono-hate/20081119/1227100016おお、面白い。ブロックソートは全然知らなかったので、ぼくも書いてみた。 import Data.List (sort, tails, transpose, elemIndex) import Data.Maybe (fromJust) encode s = (succ $ fromJust $ …

Seven Trees 解答

ref: http://d.hatena.ne.jp/ku-ma-me/20081023/p1 ref: http://d.hatena.ne.jp/m-hiyama/20081031/1225416719ポイントは檜山さんが書かれているように、T = 1 + T^2 を使って T から T^7 への式変形を構成するところです。その式変形は以下。各行は T^0 〜 …

レーベンシュタイン距離

ふとレーベンシュタイン距離 (編集距離) の計算を書きたくなったので書いてみた。わりと綺麗に書けたと思った。 def levenshtein_distance(s, t) t.chars.with_index.inject(0..s.size) do |r, (a, z)| z += 1 [z] + s.chars.zip(r.each_cons(2)).map do |b,…

Seven Trees

id:bonotake さんに教えてもらった問題。すごく面白い。 ref: http://d.hatena.ne.jp/m-hiyama/20081022/1224640248 この問題を Haskell で言うと、 data Tree = Leaf | Node Tree Tree deriving Eq type Tree7 = (Tree, Tree, Tree, Tree, Tree, Tree, Tree…

de Bruijn index の評価器

unlambda から brainfuck への変換器を作ろうしていましたが、なぜか de Bruijn index のラムダ式の評価器を Haskell で作った時点で飽きました。そんな残骸ですが、メモ代わりに公開します。de Bruijn index でも代入の定義はやっぱり複雑なんですね。 de B…

HSDL with GHC 6.6.1

Haskell の SDL binding である HSDL を GHC 6.6.1 でコンパイルするための手順メモです。 1. 必要なものをダウンロードします。 HSDL のソースコード、SDL のランタイムライブラリと開発ライブラリ (ヘッダとか) が必要です。 http://fxp.hp.infoseek.co.jp…

フィールドラベルの更新

フィールドラベルを持つ data 型の更新の文法がなんかださく感じます。 updateFoo g v = g { fooField = v } ラベルをパラメータ化できたら便利なのになあ。 update g f v = g { f = v } でもこれ、参照透明性を失うかな?よく考えてないけど。

グローバル変数のモジュール性

StateT が使えるようになったらグローバル変数みたいなものが簡潔に書けるのかなーと考えました。グローバル変数たちを集めた data 型を定義して、トップレベルは基本的に StateT GlobalVars IO () 型にする感じ。 module Main(main) where import Control.M…

猿でも持ち上げられるモナド

最近やっとモナドの持ち上げ方を理解した気分になりました。StateT + IO 限定で。State モナドを使って以下のようなコードを書いていたとき、 module Main(main) where import Control.Monad.State -- 階乗計算 fact :: State (Int, Int) Int fact = do (a, …

なんでもセミナー

情報科学なんでもセミナーの「Haskellがアセンブリになるまで」を聞いてきました。話者の中村さんは 3 週間ほどで GHC のソースコードを読んだそうです。発表もしっかりしていて、とても B3 とは思えませんでした。あと聴衆に shelarcy さんとか shinh さん…

brainfuck interpreter in Coq

Haskell 、Erlang の次のブームは Coq に違いありません。とりあえず基本ということで、Coq でひねりのない brainfuck インタプリタを書いてみました。動作例。Coq のコードが色づけできないとは何事か。 Eval compute in (finite_execute " +++++++++[>++++…

Haskell で Suffix Array

Java で Suffix Array - odz buffer なんか Haskell で Suffix Array なコードというリクエストはないけれど簡単に。とりあえず Suffix Array の構築だけ。効率とか一切無視で。 import Data.List (sort, tails) build :: Ord a => [a] -> [[a]] build = sor…

Haskell-Ruby bridge (妄想)

こんなコードが書きたいです。 require "haskell" h = Haskell.new <<HS fibs = 0:1:[ x + y | (x, y) <- zip fibs (tail fibs) ] fib = take fibs HS p h.fib(10) #=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] なにかいい方法ありませんか?</hs>

brainspace : brainfuck to whitespace

whitespace のコードはちょっと書きにくいので、brainfuck のソースコードを whitespace に翻訳するプログラムを作った。brainfuck は書けるけど、whitespace はちょっと……という人向け。http://dame.dyndns.org/misc/brainspace/brainfuck のコードに white…

bf2c : brainfuck to c

brainfuck のコードはちょっと読みにくいので、brainfuck のソースコードを C に翻訳するプログラムを作った。http://dame.dyndns.org/misc/bf2c/簡単な例を挙げると、 >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]< .…