haskell
これを書いている時点でAtCoderのHaskell処理系はGHC 7.4であり、これはプログラムに対してデフォルトで8MBのスタック制限を課す。したがって、深さ数十万の再帰を普通に書くと容易にスタック溢れによるREを起こす。このスタック制限値はコンパイル時または…
IOモナド上で動作するcall/ccを実装できることが分かったので書いておく。ただし実用に耐えるものではない。これを使うとたとえばこういうコードを書くことができる。 import Control.Applicative import Control.Monad import Data.IORef import System.IO.…
これはHaskell Advent Calendar 2013の(3+π)日目の記事です。(3 + pi)や(quot 7 8)のような単純な定数式は、ghc -Oが行なう定数畳み込みによってコンパイル時に計算される。uncurry (*) (3, max 5 2)のようなやや複雑な式も、インライン展開してから定数畳み…
変な議論してたら教えてください! 命題0 を集合、を圏、を忘却関手、を自由関手とすると、以下が成り立つ。 証明 米田の補題からなので、を示せば良い。はの左随伴だから、単位と余単位が存在して以下が成り立つ。 以下で具体的に同型射を構成する。写像と…
メモ。Haskell Reportによれば、(do a)という式の意味は(a)と同じなので、aがモナドな型を持っている必要はない。これを利用して、括弧を減らすためだけにdoを使うことができる。 import Data.Complex import Data.Monoid import Data.Text.Lazy.Builder imp…
Haskellでのデバッグといえばprintfデバッグなのではないかと思う。printfデバッグは大抵の場合うまくいくが、多相的な関数を書いているときは不便なことがある。表示したい値を文字列にする手段がない場合だ。 import Debug.Trace import Data.List mysort …
通常のレコード型は一旦定義したらフィールドを追加したりはできないが、Template Haskellを使えば似たようなことができるのに気付いたので書いてみた。次のように使う。 {-# LANGUAGE TemplateHaskell, TypeFamilies, DeriveDataTypeable #-} import OpenPr…
Haskell vs F# - Life Goes Onが気になったのでやってみた。手元にF#の実行環境がないので、元のコードを2倍高速化することを目標にしてみる。環境はLinux x64, GHC 7.0.4.最初のコード。 import Data.Array.Unboxed data Node = Node { df :: Double, branc…
Haskellコードを書いていて、インデントを揃えるのが面倒だとか、インデントが揃っているか判別しにくいということがあるかもしれない。以前は私にもよくあったのだが、二つの簡単な指針に従うことに決めてからこの種の問題に悩まされることはなくなった。の…
Haskellはオブジェクト指向言語ではないが、コードを書く上でオブジェクト指向の考え方を利用するのが便利なこともあると思うので紹介する。 オブジェクト指向とは何か オブジェクト指向という言葉に共通定義がないのは共通認識だと思う。気をつけないと議論…
iterateeって良く聞くけど何が良いの、と思ってるHaskellユーザのためのメモ。iterateeについては既に日本語の紹介が複数あるが、この記事では実装の詳細に立ち入らず、何が嬉しくてあんな奇妙なインタフェースになっているかについてだけ説明する。具体的な…
今年もICFP Programming Contestに参加していた。今回は職場のチームで出てみた。といっても開催日時が悪かったせいでたった二人のチームになってしまったが。相棒のpacakはHaskellerで、本業はISPの経営者らしい。開始前、サーバが欲しいなあと呟いたら、メ…
(追記(2011-07-30): '記号を含むprofファイルの解析に失敗するバグを修正したものをGitHub - mkotha/viewprof: A viewer of GHC .prof files with curses interfaceに上げた) +RTS -pで出力される.profファイルには呼び出しグラフが含まれていて大変役に立つ…
なにこれ Haskellは素敵な言語だと思うが、デフォルトが遅延評価であることに起因する欠点のせいで魅力を50%くらい損なっているように見える。具体的にはサンク構築/評価のオーバーヘッドとメモリリークで、特にメモリリークの実害は大きい。ならば必要な所…
eagerな言語ではfoldrはリストの長さに比例するスタックを消費する。GHCでも(+)のような正格な関数で畳み込もうとすれば同様にO(n)の振る舞いになる。 {-# OPTIONS_GHC -O0 #-} import Data.List(foldl') main = do n <- readLn print $ foldr (+) 0 [1..n] …
http://haskell.g.hatena.ne.jp/route150/20101224/1293122299を見て気になったので、エラトステネスの篩を書いてみた。n以下の素数の和を表示する。 import Control.Monad import Data.Array.ST import Data.Array.Unboxed import Data.Array.Base(unsafeRe…
Grapefruitが気になってしょうがないので、おもちゃの電卓を書いてみた。GrapefruitはFRPライブラリの一つで、定期的なポーリングを必要としないpush型の設計でありながら、push型FRPにありがちな問題をいくつか解消しているのが売りらしい。 ループのある回…
Haskellでフィボナッチ数を計算するコードとして、次のものが有名だ。 fib :: [Integer] fib = 1 : 1 : zipWith (+) fib (tail fib) これのn番目の要素を取得するコードがO(n^2)よりも遅いということを指摘した記事があった。 Haskellの「fib = 1:1:zipWith …
モナドなしで一意名生成 - www.kotha.netの裏のアイディアを検証するための例題として、λ式をη簡約するプログラムを書いてみる。構文をパース→処理→PrettyPrint、という流れを最低限要求する問題としてη簡約が手頃だと思った。構文木を表現するデータとして…
Haskellで形式言語を扱う場合、四則演算を許す数式程度なら代数的データ型が非常に良く抽象構文を表現できるが、名前の束縛が必要になるととたんに面倒なことになる。名前の衝突が厄介なので、各変数に一意の記号を付けたいのだが、たとえばData.UniqueはIO…