サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
買ってよかったもの
mkotha.hatenadiary.org
観測にノイズが乗っても対処できる二分探索が意外と簡単に書けることが分かったのでメモ。 問題 (n-1)個の整数からなる列がある。そのうち左からi個は(-1)であり、それ以外は1である。 n=6, i=3の例 -1 -1 -1 1 1クエリを繰り返すことでiを求めたい。各クエリは整数kであり、答として左からk番目の整数の値が得られる。ただし、この答にはノイズが加算される。ノイズは標準偏差σ(既知とする)の正規分布に従う。 解法 iがどの値を取るかの確率分布を持っておいて、クエリの答が得られるたびにベイズの定理に従って更新する。最初はn通りの一様分布。クエリは、得られる情報量の期待値を最大化するように選ぶ。これには、(-1)と1の境界よりも右にあるか左にあるかが半々に近い位置を選べば良い。 iの確率分布が十分に偏ったら終了。 実験 以下では、iが特定の値を取る確率が95%を越えた時点で探索を終
IOモナド上で動作するcall/ccを実装できることが分かったので書いておく。ただし実用に耐えるものではない。 これを使うとたとえばこういうコードを書くことができる。 import Control.Applicative import Control.Monad import Data.IORef import System.IO.Unsafe import Continuation (callCC, withContinuationsDo) test :: IO () test = do r <- callCC $ \cc -> return $ Right $ cc . Left case r of Left val -> do putStrLn $ "left: " ++ show val return () Right cc -> do putStrLn "right" cc "f
これはHaskell Advent Calendar 2013の(3+π)日目の記事です。 (3 + pi)や(quot 7 8)のような単純な定数式は、ghc -Oが行なう定数畳み込みによってコンパイル時に計算される。uncurry (*) (3, max 5 2)のようなやや複雑な式も、インライン展開してから定数畳み込みをすることでやはりコンパイル時に整数リテラルにまで簡約される。 これは一見万能だが、再帰的な関数が一つでもあると何もできなくなる。GHCが再帰関数をインライン化しないからだ。(sum [1])ですら実行時のループにコンパイルされる*1。 どうしてもコンパイル時に計算してほしい関数がある場合はどうしたら良いか。一つの方法はTemplate Haskell(ja)を使うことだが、特別な構文を使わなければいけないこと、-fwarn-unused-binds(ja)をはじめとし
メモ。 Haskell Reportによれば、(do a)という式の意味は(a)と同じなので、aがモナドな型を持っている必要はない。これを利用して、括弧を減らすためだけにdoを使うことができる。 import Data.Complex import Data.Monoid import Data.Text.Lazy.Builder import Data.Text.Lazy.Builder.RealFloat -- | 普通 complexInPolar :: Complex Double -> Builder complexInPolar x = fromString "(" <> realFloat (magnitude x) <> fromString ":" <> realFloat (phase x) <> fromString ")" -- | doの乱用 complexInP
Haskellでのデバッグといえばprintfデバッグなのではないかと思う。printfデバッグは大抵の場合うまくいくが、多相的な関数を書いているときは不便なことがある。表示したい値を文字列にする手段がない場合だ。 import Debug.Trace import Data.List mysort :: (Ord a) => [a] -> [a] mysort [] = [] mysort (x:xs) = trace ("inserting " ++ show x) $ -- エラー! xはshowできない insert x $ mysort xs main = print $ mysort [1,3,2,0] -- デバッグ用入力 実際のデバッグ入力であるIntegerはshowできるのだが、mysortの型からはそれが演繹できないのでshowを呼ぶことができない。ここでxを表示する
Haskell vs F# - Life Goes Onが気になったのでやってみた。 手元にF#の実行環境がないので、元のコードを2倍高速化することを目標にしてみる。環境はLinux x64, GHC 7.0.4. 最初のコード。 import Data.Array.Unboxed data Node = Node { df :: Double, branch :: [(Int, Double)] } induceBackward :: Array Int Node -> UArray Int Double -> UArray Int Double induceBackward nodes values = accumArray (+) 0 (bounds nodes) [(j, p * values ! k * df) | (j, Node df branch) <- assocs no
Haskellコードを書いていて、インデントを揃えるのが面倒だとか、インデントが揃っているか判別しにくいということがあるかもしれない。以前は私にもよくあったのだが、二つの簡単な指針に従うことに決めてからこの種の問題に悩まされることはなくなった。ので紹介する。 インデントを揃える際は、そこより左には空白しか置かない インデントは常にkの倍数個の半角スペースで行う。ここでkはプロジェクトごとの定数(以下ではk=2) 具体例 foo x y = do runThis runThat と書かずに、 foo x y = do runThis runThat と書く。 foo = bar * 2 where bar = 1 + quux quux = log 3 と書かずに、 foo = bar * 2 where bar = 1 + quux quux = log 3 と書く。 data Foo a
Haskellはオブジェクト指向言語ではないが、コードを書く上でオブジェクト指向の考え方を利用するのが便利なこともあると思うので紹介する。 オブジェクト指向とは何か オブジェクト指向という言葉に共通定義がないのは共通認識だと思う。気をつけないと議論が発散しがちなので、この記事ではオブジェクト指向の理念については扱わず、オブジェクト指向プログラミングで用いられるテクニックと、オブジェクト指向言語が提供する言語機能について専ら話題にする。オブジェクト指向の特徴として良く言われるのは次のようなものだと思う。 多態 インタフェースが同じだが異なる振る舞いをする異なる種類のオブジェクトを一つのコードで扱う機能。Haskellでは「オブジェクトを操作する関数一式」を受け渡しすることで簡単に実現できる。型クラスを使っても良い。 隠蔽 インタフェースと実装を分離し、実装を外部から見えないようにする。Has
iterateeって良く聞くけど何が良いの、と思ってるHaskellユーザのためのメモ。iterateeについては既に日本語の紹介が複数あるが、この記事では実装の詳細に立ち入らず、何が嬉しくてあんな奇妙なインタフェースになっているかについてだけ説明する。具体的なライブラリは使わず、出てくるHaskell風のコードは全て疑似コード。 データ源と処理の分離 iterateeは何をするものかを一言で言うと、データを取得しながら回すループを簡単に書くためのものだ。典型的には、ファイルやソケットからデータを受け取り、それを加工して、画面に出力したり統計を取ったりする。これを素朴に書くと、readやrecvをして、EOFを判定し、加工し、最終的な処理をするまでを一つのループ内で行うことになる。ループが大きくなってくるとこれは嫌なので、ループを分解して、データの取得、加工、最終処理をそれぞれ別々に書いて
(追記(2011-07-30): '記号を含むprofファイルの解析に失敗するバグを修正したものをGitHub - mkotha/viewprof: A viewer of GHC .prof files with curses interfaceに上げた) +RTS -pで出力される.profファイルには呼び出しグラフが含まれていて大変役に立つが、大きなプログラムだと木構造が一見して分かり辛い。特に、「この関数に時間が掛かっているのは分かったが、コストが高いのはどこから呼ばれる場合か」のようなことを知るのが面倒だ。そこで.profファイルを対話的に閲覧できるツールを書いた。 使い方 j: 一行下へ k: 一行上へ Ctrl-d: 半ページ下へ Ctrl-u: 半ページ上へ スペース: 木構造の展開/畳み l: 右へスクロール h: 左へスクロール r: ボトムアップモードへ q: 終了
なにこれ Haskellは素敵な言語だと思うが、デフォルトが遅延評価であることに起因する欠点のせいで魅力を50%くらい損なっているように見える。具体的にはサンク構築/評価のオーバーヘッドとメモリリークで、特にメモリリークの実害は大きい。ならば必要な所以外で評価を遅延させないコーディングをすれば、うっかりメモリリークを作ってしまう確率を減らせるに違いないというのがこの記事の主旨。 既に発生してしまったメモリリークに対処するのは別の問題で、有効な方法も全然違うだろう。 原則 特にそうしない必要のない限り、サンクを作ったらすぐ壊す。つまり、 let x = f y と書く代わりに、 let !x = f y と書き、 return (f x) と書く代わりに return $! f x と書く。 評価の責任 基本的に、サンクを作った者がそれを壊す責任を負うことにする。つまり、関数引数は呼び出し側
eagerな言語ではfoldrはリストの長さに比例するスタックを消費する。GHCでも(+)のような正格な関数で畳み込もうとすれば同様にO(n)の振る舞いになる。 {-# OPTIONS_GHC -O0 #-} import Data.List(foldl') main = do n <- readLn print $ foldr (+) 0 [1..n] -- O(n)スタック、O(1)ヒープ print $ foldl (+) 0 [1..n] -- O(n)スタック、O(n)ヒープ print $ foldl' (+) 0 [1..n] -- O(1)スタック、O(1)ヒープ 一方、foldrを使って効率的に実装できる関数もHaskellには存在する。例えば以下はconcatの立派な定義であり、O(1)空間で動作する*1。 concat :: [[a]] -> [a] concat =
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(unsafeRead, unsafeWrite, unsafeAt) import System.Environment sieve :: Int -> UArray Int Bool sieve n = runSTUArray $ do arr <- newArray (0, n) True let end = floor $ sqrt (fromIntegral n) writeArray arr 0 Fal
プリプロセッサメタプログラミングの話。 Cプリプロセッサ上で値の列を表現するためのデータ構造の一つとしてsequenceというのがある(Boost.Preprocessorの用語)。 他の言語でいうリストや配列に似たもので、以下のような形をとる。 (0)(1)(2)(3) /* 0から3までの整数のsequence */ (signed char)(short)(int)(long) /* C++の符号付き整数型のsequence */ なお、空のsequenceは扱いがいろいろ面倒なのでこの記事では無視する。 リスト風のデータ構造ならばもちろんfold演算が欲しい。Cプリプロセッサ上のプログラミングは関数型プログラミングであることを考えればなおさらだ。 このためにBoost.PPにはBOOST_PP_SEQ_FOLD_LEFTとBOOST_PP_SEQ_FOLD_RIGHTというマクロが
Haskellでフィボナッチ数を計算するコードとして、次のものが有名だ。 fib :: [Integer] fib = 1 : 1 : zipWith (+) fib (tail fib) これのn番目の要素を取得するコードがO(n^2)よりも遅いということを指摘した記事があった。 Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」はとても遅い - 西尾泰和のはてなダイアリー 実はこの現象は、リストfibを先頭から順番に使っていった場合には起こらない。(!!)などでリストの途中の要素を取得して、その値をいきなり評価した場合に発生する。以下が実証用コード。 {-# OPTIONS_GHC -O3 #-} import System.Environment(getArgs) -- 最初のfib fib :: [Integer] fib = 1:1:zi
出た。 今年の課題は、車と燃料を設計/販売して金儲けというもの。といってもリアルな設計ではなく、車は特定の形の連立不等式で、燃料はその解で、それぞれ表現される。車と燃料をセットで提出するのが基本で、さらに他人の設計した車に適合する燃料を作ることができればその利益の一部を奪えるというルール。 追加要素として、車と燃料は三進数で符号化して提出しなければならないが、そのエンコード方式は非公開。さらに燃料については三進コードを直接送るのではなくコードを生成する回路(これも詳しい仕様は非公開)を送るというものだった。非公開仕様についてはサーバからのエラーメッセージをもとに試行錯誤で把握することが要求された。 経過 開始直後。課題を読む。本題に到達するまでのハードルの高さに驚く。キー回路を読もうと紙の上で試行錯誤していたら構文は比較的すぐに分かった。 回路を組むためのコードをHaskellで書く。深く
Haskellで形式言語を扱う場合、四則演算を許す数式程度なら代数的データ型が非常に良く抽象構文を表現できるが、名前の束縛が必要になるととたんに面倒なことになる。名前の衝突が厄介なので、各変数に一意の記号を付けたいのだが、たとえばData.UniqueはIOモナドだし、似た機構を自分で作るにしても大域状態を扱う必要がある。これは(\x -> x)のような閉じた式を表現するデータを作るのにも大域状態を参照しないといけないということで、非常に不便だ。 解決の方向はいくつか考えられるが、なんとかして一意な名前の生成を手軽にできないか考えてみる。単純にnewUniqueをunsafePerformIOでIOモナドの外から無理矢理呼ぶのは、参照透明性を無茶苦茶に破壊するので話にならない。そこで少し工夫する。 fresh :: (Unique -> a) -> a fresh f = f $ unsa
このページを最初にブックマークしてみませんか?
『www.kotha.netの裏』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く