本では全然ない。Haskellの標準ライブラリ。
Haskellは、なかなか楽しい。Preludeを読んでいて、特に楽しかったのは、やっ
ぱり、List関係の節。
Ruby(1.8)のinjectみたいなやつ。
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
zを初期値として、関数を左からアプライした結果を蓄積していく。
foldl (+) 0 [1..10]
の結果は、55。
foldl (flip (:)) [] [1..10]
の結果は、[10,9,8,7,6,5,4,3,2,1]。これは、reverseの定義だったりする。
関数を左からアプライした結果をListにしていく関数scanl
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl f q xs = q : (case xs of
[] -> []
x:xs -> scanl f (f q x) xs)
を使えば、
take 10 a where a=1:scanl (+) 1 a
=> [1,1,2,3,5,8,13,21,34,55]
フィボナッチ数列は、
take 10 a where a=scanl (+) 1 a
=> [1,2,4,8,16,32,64,128,256,512]
2**nとあんまり変わらないんだなあ、とか思ってしまうのだ。
rubyではおなじみ、iterateは、haskellでは、
iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)
という関数が用意されている。これは、xにfを何度もaplyしていって得られる
結果を配列にしていく。
take 10 (iterate (+ 1) 1)
=>[1,2,3,4,5,6,7,8,9,10]
(Rubyの意味でのiterateは、mapとか、foldlの方が近いと思うが)。
こういうあたりを見ていると、いろいろ考えさせられてしまう。
で、先日、Haskellおもしろいっすよ、と言ったら、「そういうのはバッドノ
ウハウちゃうか」と言われたが、即座に否定するのは難しかったが、いやいや、
こんなおもしろいものが、バッドノウハウであろうか。
そもそも、「本来は知りたくもないノウハウ」がバッドノウハウであるが、い
やいや私は知りたくてしょうがないんだから。
- 遅延評価
- オブジェクト表現から関数表現へ
の2点。
一つ目の遅延評価は、その名の通り、後で評価すること。
例えば上でも挙げた、フィボナッチ数列(a=scanl (+) 1 a) から、偶数項だけ
のListを作る。
f::[Int]
f = let b=filter even a
in b where a=1:scanl (+) 1 a
無限個 要素があるが、必要になるまで計算されないから、結果はすぐかえる。
main :: IO ()
main=print (take 10 f)
main関数で、fの最初から10個だけ表示してもらう。この時はじめて計算が実
行され、
[2,8,34,144,610,2584,10946,46368,196418,832040]
という結果がでるのであった。(これ、よく考えたら、3つ飛びに出てくるだけ
だ)。
Lispの勉強をしたときは、末尾再帰で繰り返しすることについて考えさせられ
るものがあったが、haskellでは、再帰というか、遅延生成されるリストへの
mapのようなものとして繰り返しを考えるべきなのだろうか。
もう一つは、"オブジェクトレベルでの表現から関数レベルの表現へ変換"
(「やさしいHaskell入門」より)で、効率が上るという点。
(1)
let a=take 100 (repeat 1)
b=map show a
str=foldl1 (++) b
in str
(2)
let a=take 100 (repeat 1)
b=map (\s-> (show s ++)) a
str=foldl1 (.) b
in str []
(1)は、"1"++"1"++"1"++ .... "1" と、100個ならべたもの。
(2)は、(("1"++) . ("1"++) . ("1"++) . .... ("1"++)) [] と関数の合成
にしたもの。
並べる数が10を超えるあたりで逆転し、関数の合成の方が効率が良くなる。
考えさせられてしまうな。
$Date: 2003/05/05 09:10:12 $ (GMT)