はてなブックマーク

mkotha さんに直してもらったりして、Haskellのコードはだいぶ速くなりました。どうも２重ループの内側がボトルネックのようなので、そこを展開して、データ構造も変えて、UNPACKプラグマは効くので残して、正格評価を１ヶ所だけ。性能と可読性のバランスがそこそことれたかなと思ってます。C++ や F# のコードにも同じような改修を加えたら、Haskell はまた抜かれてしまいました。まぁでも、目くじら立てるほどの差でもないので、そのままにしています。 実行環境が Windows というアドバンテージがあるとはいえ、C++ も超える F# の健闘が光ります。明示的な副作用がない関数プログラミングでこれだけ速いとうれしい。コード書いてても気持ちがいいし、Microsoft でなければもっと流行っていいはず。 最終形のコードを以下に載せておきます。 ついでに Scala でも書いてみました。

VB .NET で書かれたプログラムを速くしろと言われて、Haskell と F# で書き換えたりしています。僕の目論見ではHaskellの方が速くなるはずで、そしたら『F# もいい言語ですけどね、やはり速度を求めるならネイティブ・アプリケーションでないと。』とか何とか言って、Haskell 化してしまう予定でした。だって僕は F# 初心者だし、Haskell は C++ にも負けないわけだし、Haskell が速いに決まってるじゃないですか。 ところが実際に試してみたら、F# の方が速くなってしまいました。それも２倍以上。というわけで、図らずも自分自身の Haskell 力の無さを露呈してしまったわけですが、それはともかく、Haskell が遅いとかいう汚名を着せられてしまうのは、避けなくてはなりません。 でも、ごめんなさい、僕の能力では限界です。 世の Haskeller のみなさま、

何となく触ってみました。以下に体験記を。 Lazy K の入力はチャーチ数のリストとして与えられます。出力もチャーチ数のリストとして構成。Haskell の interact が最初から備わっているような感じ。 なので、入力をそのまま出力する echo サーバは以下のように書けます。 I"K〜"とすれば、入力を無視して"〜"を出力します。 Hello, world! は大変そうなので、まずは一文字出力に挑戦。作るのが簡単そうな"@"(0x40)を選びました。 最初に書いたコードはこんな感じ。 K (S(KS)K (S(S(K(S(KS)K))S)(KK)I (K(SII(SII(S(S(KS)K)I))))) (S(S(K(S(KS)K))S)(KK)I (S(S(KS)K)(S(S(KS)K)I)(S(S(KS)K)I(S(S(KS)K)I)))))簡単に解説すると、K (cons 64

いつも忘れて、その度にぐぐってるので、メモ。 コンパイル時に -prof -auto-all オプションをつける ghc --make -prof -auto-all hoge.hs実行時に、+RTS -p オプションをつけて、出力される 〜.prof ファイルを読む ./hoge.exe +RTS -p -RTS特定の式のコストを見たいときは、ソースコード中でコスト集約点を指定（Set Cost Center）する hoge = {-# SCC "hoge" #-} <expression> 詳しくは、第5章 プロファイルを取る を参照

以前にもエントリを書きましたが、Readerモナドがさっぱり分からないので、もう一度勉強してみました。 あまり深く考えずに Reader a を a -> と読み替えると、関数の型は以下のようになります。 関数 型 等価な関数 (>>=) (a->b) -> (b->a->c) -> a -> c (=<<) (a->b->c) -> (b->a) -> b -> c (>>) (a->b) -> (a->c) -> a -> c flip const return a -> b -> a const ap (a->b->c) -> (a->b) -> a -> c <*> liftM (a->b) -> (c->a) -> c -> b (.) ask a -> a id local (a->a) -> (a->b) -> a -> b flip (.) ちょっと確かめてみると、確かに等

注：この文章は Haskell 布教のため、 Haskell を知らない人向けに書いています。なので、ちょっとでも分かりにくいところはどんどん指摘してください。 しばらく前に、hasekll-jp のメーリングリストで Haskell の型クラスの体系が話題になっていたのですが、そこで衝撃を受けたメールがありました。 http://www.sampou.org/cgi-bin/w3ml.cgi/haskell-jp/msg/463 何に驚いたのかを以下に説明したいと思います。 リストと要素の変更 Haskell にはリストというデータ構造があります。他の言語と同じように特定の種類の要素を複数格納していて、インデックスを指定すると要素を取り出すことができます。 list = [1,5,7,6,2,8,3,0,9,4] -- 0から1までの整数を格納したリスト val = list !! 3

Kコンビネータと真偽値に関する話題が挙がっていたので、それを使って何か書いてみようと思いました。 条件分岐と言えば FizzBuzz。以下のようなプログラムを考えます。 main = mapM putStrLn [ max (show n) $ fizz n ++ buzz n | n <- [1..100] ] fizz n = if mon n 3 == 0 then "Fizz" else "" buzz n = if mon n 5 == 0 then "Buzz" else "" まずは以下のように if' を定義しますが、これだけだとまだあまり変わっていません。 Haskell 標準の Bool 型を使っているし、パターンマッチで結局 if 相当のことをやっているからです。（ポイントフリーで書けない！！） fizz n = if' (mod n 3 == 0) "Fizz" "

ちょっと前に haskell-cafe で速い素数の求め方が話題になっていました。 どんなもんだか確認した結果を記録。 僕がよく使ってたコードはこんな感じ。改めて見るとツッコミどころ満載です。 106 番目の素数を求めるのに手元のマシンで 2 分以上かかります。 primes0 = 2 : filter isPrime0 [3..] isPrime0 x = all ((/=0).mod x) $ takeWhile (<= (floor$sqrt$fromIntegral x)) primes0 平方根または二乗を求めるのに、いちいち整数から浮動小数に変換するのはコスト高すぎ 偶数も全てチェック対象にしているのは無駄 mod より rem の方が速い（これはなぜ？） というあたりを修正したのが↓のコード。1 分 20 秒。 primes1 = 2 : 3 : filter isPrime

Scala の for 構文（とりあえずこう呼びます）がただのリスト内包表記なら、いちいちモナドとか言わない方がいいんじゃない？とかいうことを昨日書いたのですが、for 構文は Seq 型だけじゃなくて Option 型とか他の「モナドっぽい」型にも使えるよ、ということをコメントで教えていただきました。 本当だ、こことかこことかに書いてある。明らかに調査不足ですね、すみません。 たとえば以下の2つの関数 fSeq と fOpt、引数や戻り値の型は違いますがまったく同じように定義できます。 これは便利だ。前言撤回します。モナド、モナド。 scala> def fSeq (mx:Seq[Int], my:Seq[Int]) = for (x <- mx; y <- my if (x+y)%3==0) yield x*10+y fSeq: (Seq[Int],Seq[Int])Seq[Int]

@autotaker1984 さんの以下の記事について考えました。 永続リアルタイムキューのHaskell実装と計算量解析 - autotaker's blog head / tail するときに、reverse さえ完了していれば問題ない、だから snoc で停止計算を進行させる必要はない、というのはなんとなく説得力があります。 けれども PFDS では、 rotate が始まるときに停止計算がすべて完了していること（負債を完済していること）にこだわっていました。 それは、停止計算が重なると再帰的な呼び出しで計算量が増えるからです。 たとえば空のキューに 1 から 15 まで snoc すると、frontList は以下のような状態で、go 関数の呼び出しが再帰的になります。 go [] (go [] (go [] (go [] [] [1]) [3, 2]) [7, 6, 5, 4])