haskell / Drkcore

Real World Haskell 15章

Sat, 09 Oct 2010 18:28:36 +0900

モナドを使ったプログラミング

Real World Haskell―実戦で学ぶ関数型言語プログラミング
Bryan O'Sullivan,John Goerzen,Don Stewart
オライリージャパン / ￥ 3,990 ()
在庫あり。

持ち上げの一般化(15.2)

liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
Prelude Control.Monad> :t liftM

liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r
Prelude Control.Monad> :t ap
ap :: (Monad m) => m (a -> b) -> m a -> m b

liftM(N)はliftMとapを使って一般化できる。

Readerモナドを大体理解した(15.6)。

newtype Reader e a = R { runReader :: e -> a }

instance Monad (Reader e) where
    return a = R $ \_ -> a
    m >>= k  = R $ \r -> runReader (k (runReader m r)) r

ask :: Reader e e
ask = R id

askで得た環境を引き回す。

*Main Data.Char> runReader (ask >>= \x -> return (x*3)) 2
6

askで常に同じ環境が返ってくる、読み取り専用のStateみたいなもんか。

ポイントフリースタイルのhead

Wed, 03 Jan 2007 20:22:37 +0900

普通のhaskellプログラミングの216ページに

ポイントフリースタイルへの書き換えは脊髄反射の速度でできるようにしてください。

と書いてあったのだけど、脊髄どころか反射すらできない。

firstNLines :: Int -> String - String
firstNLines n = unlines . take n . lines

nを押し出すのってどうやるんだろうか?

追記07.01.03

解決したヨ。

ポイントフリーなhead.hs

Wed, 03 Jan 2007 20:18:01 +0900

下の式を完全なポイントフリースタイルにする方法を色々と考えてみたんだけど。

firstNLines n = unlines . take n . lines

結局分からんかったので、mixiで聞いてみたらさくっと教えてもらえた（ありがたい）。

unlines . take n . lines
(unlines . take n) . lines
(. lines) (unlines . take n)
(. lines) ((unlines .) (take n))
((. lines) . (unlines .)) (take n)
((. lines) . (unlines .)) . take
(. lines) . (unlines .) . take

.って演算子として考えればよいらしい。だから、左側を取るように書き換えてやればいいのか。

Prelude> 5 + 7
12
Prelude> (+ 7) 5
12

(+)だとこんな感じ。

型を確認すると

Prelude> :type (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

.は(b -> c)と(a -> b)という関数をとってa->cという関数を合成する関数(二項演算子?)なのか。

(.) :: (b -> c) -> (a -> b) -> (a -> c)

関数合成で、変数が消えていくのは、こういうことなのね。

相変わらずモナドが

Mon, 25 Sep 2006 22:32:35 +0900

モナドで躓いて以来、ちょっとご無沙汰していたhaskellだが、ちょっとまとまった時間ができたので、この週末でじっくり考えてみた。

モナドだけに、読むたび必ず睡魔に襲われる（参照透明性確保！）でも理解度はちょっぴり向上してるっぽい(つまり副作用)。

檜山正幸のキマイラ飼育記はjavascriptを例にして、純関数にすること（参照透明性の確保?）と型を揃えることが重要っぽいあたりが理解できた。
で、HaHaHa!では思考をもうチョイ広げて、とりまく環境の変化ということに思いをめぐらせればいいということを理解した。特に図がわかりやすくて、かなり理解が進んだと思う。
で、それから、実際にperlの例を見るとを～とか思う。

変数の代入をIOと考えればtieって参照透明性を確保しつつ、副作用を発生させることができるのね。この場合にいわゆるモナド則は成り立つのかなと考えてみたけど、なんとなく成り立つのかなと思ったり。

と、ここらへんまで理解した気になって、再度ふつうのhaskellを。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門
青木峰郎
ソフトバンククリエイティブ / 2940円 ( 2006-06-01 )

なんとなくわかってキテルっぽいが、じゃぁ、MaybeモナドとかListモナドって何なのヨっていうか、モナドって一体何さ?っていうあたりがわからなくなってきた。さらにperlのtieなんかで実装できるってことは、モナド則っていうのは結局なんなのってのがよくわからん。

ふつうのhaskellに
モナドを定義の観点からみるならばモナド則がすべて
とあるように、モナド則を感覚で理解しなければならんのかな。

All About Monads

ほんとうにモナドを理解するには、モナドを使ったコードを経験することが最良の方法です。

というわけで、コードを書こう。

haskellだとフィボナッチ数列を表現すればいいのか

Sat, 19 Aug 2006 18:55:01 +0900

コメントでhaskellでフィボナッチの別解をもらったが、パッと見てもなぜこれでフィボナッチ数列ができるのかいまいちわからんかったので、よく読んでみたヨ。

まずは型チェック。見ればわかるとおりfibはリストを返す関数ですな。つまり、fibを実行するとフィボナッチ数がどんどこどんどことそれこそとめどなく溢れてくる(はず)

fib :: Num a => [a]
fib = 0:1:zipWith (+) fib (tail fib)

これを　fib.hsという名前で保存してghciで実行してみる。

$ghci
*Main> :l fib.hs
*Main> fib

をを～。凄い勢いでフィボナッチ数列がどんどこど(以下略)。ちなみにlengthでリストの長さをはかってみると、プロンプトがかえってこないゾ。さすが無限リスト。

zipWithの型とtailの型はこんな感じ。

Prelude> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Prelude> :t tail
tail :: [a] -> [a]

zipWithは高階関数で、+関数をfibとtail fibに適用して新しいリストをつくるわけですな。tailは先頭の要素を取り除いたリストを返す関数だから、、、うーんやってることはわかるんだけど、イマイチイメージできん。

と悩んでたら、Wikipediaに書き下されてる表をみつけて納得した。perlで同じことやろうとするとまず有限個の要素をもつ配列があってみたいなところから始まるから、こういう表現はできないな。というわけで、目からうろこっていうか、ちょっと感動した。

ここで考えたようなn-1番目とn番目のフィボナッチ数が与えられたときにn+1番目のフィボナッチ数を求めるということを考えるのではなくて、そもそもフィボナッチ数列とは何かを考えて、それを無限リストとして表現することを考えればよいんですよと。

となると、リスト内包表記も感動するような綺麗さダ。

fibs = 0 : 1 : [ a+b | a <- fibs | b <- tail fibs ]

Haskell - Wikipedia

GHCの並列リスト内包表記(GHCの拡張は特別なコマンドラインフラグによって有効にしなければならない。

とあるのが、なにが問題なんだかわからんので、とりあえず実行してやろう。

fib4.hs:1:15: Illegal parallel list comprehension: use -fglasgow-exts
Failed, modules loaded: none.

デフォルトだと、同じリストが複数でてくるような表記の仕方(この場合はfibs)は問題あるということなのかな

ghci -fglasgow-exts

とオプションを指定して実行することで、OK。をを～。凄い勢いでフィボナッチ数列がどんどこど(以下略)。

haskell素敵過ぎ

haskellでフィボナッチそしてPerlで書いてみた

Thu, 10 Aug 2006 22:44:11 +0900

普通のhaskellプログラミングを読み終えて、なんか次に読むものないかなと探していたら、webarchiveに面白そうなページがあることを知ったので、ダウンロードして読んでます。

3回目の講義資料に、タプルを使って高速にフィボナッチ数を計算する話があったので、なんでそうなるのかを理解するために手で書き下してみた。

普通に書くとこんな感じ(fib)。

fact :: Int -> Int
fact n
  | n == 0  = 1
  | n > 0   = fact (n-1) * n

書き下すと、計算量があっという間に増えていくことがわかる。

fib 5
=> fib 3 + fib 4
=> (fib 1 + fib 2) + (fib 2 + fib 3)
=> (fib1 + (fib 0 + fib 1)) + ((fib 0 + fib 1) + (fib 1 + fib 2))
=> (fib1 + (fib 0 + fib 1)) + ((fib 0 + fib 1) + (fib 1 + (fib 0 + fib 1)))

タプルを使った例(fastfib)

フィボナッチ数列を効率良く計算する方法を考えよう．前に見たとおり，フィボナッチ数列の各項は，その前の二つの項の和である．逆に言えば，二つの連続した項の値が与えられれば，次の項を計算するのは簡単なのだ．

fibStep :: (Int, Int) -> (Int, Int)
fibStep (u, v) = (v, u+v)

fibPair :: Int -> (Int, Int)
fibPair n
  | n == 0    = (0, 1)
  | otherwise = fibStep (fibPair (n-1))

fastFib :: Int -> Int
fastFib = fst . fibPair

コードを眺めただけではなんで速くなるのか実感がわかなかったので、書き下してみる。

fastFib 5
=> fst (fibPair 5)
=> fst (fibStep (fibPair 4))
=> fst (fibStep fibStep (fibPair 3))
=> fst (fibStep fibStep fibStep (fibPair 2))
=> fst (fibStep fibStep fibStep fibStep (fibPair 1))
=> fst (fibStep fibStep fibStep fibStep fibStep (fibPair 0))
=> fst (fibStep fibStep fibStep fibStep fibStep (0, 1))
=> fst (fibStep fibStep fibStep fibStep (1, 1))
=> fst (fibStep fibStep fibStep (1, 2))
=> fst (fibStep fibStep (2, 3))
=> fst (fibStep (3, 5))
=> fst (5, 7)
=> 5

をを、タプルにすることで、計算量が減ってます、自分で展開していくとなるほどとよくわかる。

さて、最近Higher-order Perlを読んでいる僕としては、これをperlで書いてみたくなるわけである。

#!/usr/bin/perl

use strict;
use warnings;

sub fibStep {
    my $n = shift;
    return [$n->[1], $n->[0] + $n->[1]];
}

sub fibPair {
    my ($n, $fs, $fp) = @_;
    return [0,1] if ($n == 0);
    return $fs->($fp->($n-1,$fs,$fp))
}

sub fastFib {
    my $n = shift;
    my $fs = \&fibStep;
    my $fp = \&fibPair;
    my $fib_num = $fp->($n,$fs,$fp);
    return $fib_num->[0];
}

my $number = shift;
print fastFib($number)

サブルーチンのリファレンスを引数にとらないといけないのがhaskellと異なるとこかな。あとは書いてて思ったのは関数の型を書くとプログラムの流れが理解しやすいナァと。

実行すると一瞬で計算が終わる（速い!）

実際に処理の流れを追うために-dオプションを付けて実行してsを連打すると、main::fibPairがどんどん実行されて$nが0になったところで今度はmain::fibStepが次々実行されていく様がわかる。

Higher-order Perlの5章にもフィボナッチ数列のことが書いてあるのだが、まだそこまで読み進めていない。(今3章突入したところ)

Higher-Order Perl: Transforming Programs with Programs
Mark Jason Dominus
Morgan Kaufmann / 6402円 ( 2005-03-28 )

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門
青木峰郎
ソフトバンククリエイティブ / 2940円 ( 2006-06-01 )

haskellを勉強しながら、Higher-order Perlを読むと、色々新たな発見があって楽しい。

Meadowでhaskellモード

Thu, 20 Jul 2006 22:21:58 +0900

ふつうのHaskellプログラミングも、とうとう第三部のWIKIをつくろうの章に突入。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門
青木峰郎
ソフトバンククリエイティブ / 2940円 ( 2006-06-01 )

でも、第三部は実際のコードのポイントだけ解説なので、サポートページからコードをダウンロードしてきてつきあわせながら読む感じになるので、Meadowでソースコードを開いて本を読んでる。

で、perlとかjavascriptは色がついてて見やすいのに、、、Meadowにhaskellモードってないのかなぁと思って探したらあった。

これでかなりコードが読みやすくなった。

あと本を最後まで読んでみての感想だが、ふつうのHaskellプログラミングは一部、二部と三部の具体事例の間にはかなり開きがあるような気がした。二部と三部の間に数学的な問題を事例として扱う部もあったほうがいいような。

というわけで、「連載: Haskellプログラミング」なんかを読んで解くといいかもしれん。

モナドで躓く

Tue, 11 Jul 2006 22:34:25 +0900

ふつうのHaskellプログラミングも、とうとう11章へ。中盤も佳境をむかえております。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門
青木峰郎
ソフトバンククリエイティブ / 2940円 ( 2006-06-01 )

モナドが～～

わかりません、さっぱり。他の言語での例があったので少し読んでみた。

檜山正幸のキマイラ飼育記 - 世界で一番か二番くらいにやさしい「モナド入門」

振り返れば我々は；関数から副作用を取り除き（汚れ作業はCountupMainに押しつけ）、代わりに戻り値に副作用の意図を詰め込み、それによって失われた関数結合の自由さを関数の拡張により取り戻しました。

javascriptもperlのコードもなんとなくわかったような気にはなったんだけど、ふつうのHaskellプログラミングに戻ると混乱してしまうヨ。

週末にでも幾つかコードを書いてみてよく考えることにしよう。

http://del.icio.us/kzfm/haskell

HaskellでBioinformatics

Mon, 03 Jul 2006 21:56:55 +0900

本日普通のHaskellプログラミングの7章まで読み終えた。そろそろ、具体的な例題解いてみたいなぁと思ったが、3部13章のWIkiをつくってみようの章まではあと5つもある。今のとこ、ここまで読んで、実用Perlプログラミングみたいに他の言語との違いみたいなページを割いてくれるとよかったりと思った。それ以外は、unixのコマンドをtailとかheadとかをhaskellで書こうみたいな感じにすすむので理解はしやすいヨ。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門
青木峰郎
ソフトバンククリエイティブ / 2940円 ( 2006-06-01 )

実際に、どんな感じの問題に適用すんのがいいのかなぁとか、考えたときに、ゲノムみたいな大きい配列操作すんのに適してるも。もしかしてbioinformaticsでなんかあるかなと探したらあった。

論文あったのでアブスト眺めたけど、DPってhaskell向きなのかな？まだ、いまいちわかってなさげ。

Rによる統計的プログラミングでRと比較しているのだから統計的な(というより数学的な)記述にむいているのは感覚的にわかるんだけどなぁ。

ということはchemoinformaticsでの利用例あるだろ、とか思うんだが見当たらない。

perlで高階関数とカリー化

Sun, 25 Jun 2006 23:27:10 +0900

先週は電車通勤+歩きで仕事場を行き来したので、電車の中で、英語漬けで英語のトレーニングしてみたり、普通のHaskellプログラミング読んだりと、電車通勤はなかなか有意義なことに気付かされた。特に普通のHaskellプログラミングは第一部を読み終えたことで、高階関数と変数の束縛というものがわかったような気がした?

、、、、したのかどうかまだよくわからんので、自分の理解力を認識するために少し書いてみた。

まず、言葉の定義を。

変数の束縛
(例えば)関数という値があり、それが変数名を束縛している
高階関数
関数を返したり引数にとったりする関数
変数が関数に束縛されているから、関数を変数として扱うことが出来る?
それとも関数を変数として扱うことことが出来れば高階関数はつくれるのか?

perlでも変数を束縛することが出来れば高階関数など扱えるのかなと。クロージャ使えってことか？と思って調べて見ると面白そうなのが。

（って全部一度は見たことあるじゃん。でもワカンネとか言って放り出した気が、、、、）

ぱるも日記ではカリー関数を作る例が示されていたが、関数を返す高階関数の例ですな。カリー化に関しては、これなど面白かった。

torus solutions!は僕がblosxomをいじくるときにかなり参考にさせてもらったサイトです。

XML を Perl の高階関数で。 : torus solutions!

XML::LibXML で XML を作るときに、いちいち createElement とか appendChild とか書くのに飽きてきたので、高階関数版を作ってみた。

これも、関数を返すといってよいのでしょう。

関数を引数にとる高階関数をperlで書けるのだろうか？というのが気になるところだが、関数のリファレンスを引数にとる関数を書けばいいのかなと思ってこれまた調べてみた。

http://d.hatena.ne.jp/cranebird/20060308/1141829356

ここまでの関数を返す関数とか関数を引数にとる関数を考えると、perlでの(関数による)変数の束縛ってのは、関数のリファレンスを変数として扱うことでなされると考えてよいのかな。

Higher-Order Perl: Transforming Programs with Programs
Mark Jason Dominus
Morgan Kaufmann / 6402円 ( 2005-03-28 )

Higher-order Perlも気になる

haskell / Drkcore

Real World Haskell 15章

ポイントフリースタイルのhead

追記07.01.03

ポイントフリーなhead.hs

相変わらずモナドが

haskellだとフィボナッチ数列を表現すればいいのか

haskellでフィボナッチ そしてPerlで書いてみた

Meadowでhaskellモード

モナドで躓く

HaskellでBioinformatics

perlで高階関数とカリー化

haskellでフィボナッチそしてPerlで書いてみた