サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
大谷翔平
rst76.hatenablog.com
以下の記事は、 R 教授による S 大学での講義録を Haskell Advent Calendar 2012 のために転載したものである。 はじめに えー、それでは、今年最後の授業を始めたいと思う。今日は『究極の関数型言語による至高の Hello, world!』について講義することにしたい。 “究極”の関数型言語が何であるかについては諸説あろうが、ここでは SKI コンビネータ計算を指すものとする。また“至高”の定義を、最も簡潔であること、すなわち最も短く記述されていることと定める。 諸君は第一プログラミング言語として Haskell を選択している者がほとんどであろう。当初この講義も Haskell をベースに行おうと考えていた。だが、Haskell は非常に巨大な言語となってしまっており、言語仕様を把握するだけでも難しい。だいたい STG が Spineless Tagless G
mkotha さんに直してもらったりして、Haskellのコードはだいぶ速くなりました。どうも2重ループの内側がボトルネックのようなので、そこを展開して、データ構造も変えて、UNPACKプラグマは効くので残して、正格評価を1ヶ所だけ。性能と可読性のバランスがそこそことれたかなと思ってます。C++ や F# のコードにも同じような改修を加えたら、Haskell はまた抜かれてしまいました。まぁでも、目くじら立てるほどの差でもないので、そのままにしています。 実行環境が Windows というアドバンテージがあるとはいえ、C++ も超える F# の健闘が光ります。明示的な副作用がない関数プログラミングでこれだけ速いとうれしい。コード書いてても気持ちがいいし、Microsoft でなければもっと流行っていいはず。 最終形のコードを以下に載せておきます。 ついでに Scala でも書いてみました。
VB .NET で書かれたプログラムを速くしろと言われて、Haskell と F# で書き換えたりしています。僕の目論見ではHaskellの方が速くなるはずで、そしたら『F# もいい言語ですけどね、やはり速度を求めるならネイティブ・アプリケーションでないと。』とか何とか言って、Haskell 化してしまう予定でした。だって僕は F# 初心者だし、Haskell は C++ にも負けないわけだし、Haskell が速いに決まってるじゃないですか。 ところが実際に試してみたら、F# の方が速くなってしまいました。それも2倍以上。というわけで、図らずも自分自身の 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
会社の勉強会で、Haskell による確率プログラミングについて話しました。 元ネタは Oleg さんの論文(Probabilistic Programming)です。OCaml で書かれていたプログラムを Haskell に翻訳しながら解説しました。 もともとの論文の主張は、木探索として定義したモデルを継続渡し方式(Continuation-Passing Style / CPS)にすることで効率化できる、さらに限定継続を利用することで、継続を意識せず直接方式(Direct Style)で書けるようになるというものでした。 木探索から CPS にすることで効率化という流れは Haskell でも同じなのですが、限定継続を利用しても直接方式では書けないため、あまり嬉しくありません。でも Haskell には do 記法があるので、モナドとして定義すれば擬似的に直接方式で書けてハッピーという
いつも忘れて、その度にぐぐってるので、メモ。 コンパイル時に -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])
このページを最初にブックマークしてみませんか?
『Life Goes On』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く