すごいHaskell五章（後半）
畳み込ぞ
「基底部は空リストとし、x:xsパターンを使ってリストを先頭要素と残りのリストに分解する」
というパターンを関数にしたものがfold…多分。
毎度のことだが、最初の概要を見ただけじゃ何もわからない。例を見て、自分で処理を追わないと。
本の例はsumだったので、productを実装した。（+を*にして、アキュムレータの初期値を1にしただけだけど…）
product' :: (Num a) => [a] -> a product' xs = foldl (\acc x -> acc * x) 1 xs
部分適用を利用すると下のようになる。
product'' :: (Num a) => [a] -> a product'' = foldl (*) 1
ここでの部分適用は2つあって、1つはセクションを使った(*)。二変数を取る関数に直接当てはめられる。
もう一つはfoldl。二変数関数とアキュムレータの初期値が与えられてるので、後はリストをとるだけの関数になる。
ちなみに再帰で書くと下のようになる。
product' :: (Num a) => [a] -> a product' [] = 1 product' (x:xs) = x * product' xs
foldは今のところ、リストの要素を1つづつとって、アキュムレータとその要素で関数を適用するイメージを持ってる。
foldのアキュムレータの初期値と、再帰の基底部って同じでいいのかな…？まだ分からんけど。
あと、:より++の方が処理がずっと重いらしい。
foldrによるelemの実装は、本の例からさらに部分適用を利用すると下のようになる。
elem'' :: (Eq a) => a -> [a] -> Bool elem'' y = foldr (\x acc -> if x==y then True else acc) False
引数に取った「探したい要素」と比較しないといけないから、1つは引数を取る必要があるはず。リストはfoldrの部分適用でいい。ただ、fodrが右から探索してるのなら、無限リストに適用できるのはなんでだろう。あと、foldlが左から探索…あ、これはいつまでたっても終わりにたどり着かないから無限リストに適用できないのか。elemならいけるだろと思ったけど、Trueになったら終了じゃなくて、リストの終端にきたら終了だから。
elemをfoldlで実装してみる。
elem''' :: (Eq a) => a -> [a] -> Bool elem''' y = foldl (\acc x -> if x==y then True else acc) False
有限なリストに適用してみる。
ghci> elem''' 1 [1..10] True
普通に動く。でも無限リストに適用してみると…
ghci> elem''' 1 [1..] <interactive>: out of memory
止まらなくなってメモリ切れした。
リストの最初（最後）の要素をアキュムレータの初期値に使うfoldl1、foldr1
minimunを実装した。
minimum' :: (Ord a) => [a] -> a minimum' = foldl1 min minimum'' :: (Ord a) => [a] -> a minimum'' = foldr1 min
これだとfoldl1、foldr1ともに、同じように動作するっぽい。（スピードは違うかも）ちなみに、無限リストを与えると両方とも止まらなくなる。
ghci> minimum' [1..10] 1 ghci> minimum'' [1..10] 1
そうか、productはfoldl1で実装したほうが短くなるのか。（追記：foldl1じゃねーよ。後で読み直したら、普通にfoldlで定義されてた。）でも標準のproductは空リストを渡しても1が返ってくるから、foldか再帰で実装されてるんじゃないかと思う。sumも0が返ってくる。
ghci> product [] 1 ghci> sum [] 0
reverseがfoldl1で実装できないのは、アキュムレータが最初は要素なのに次からリストになっていくからだと思う。(\x y -> [y] ++ [x])でも(\x y -> y : [x])でも都合が悪い。
そして、flipの動作がまだよく分かってないことに気付いた。flip (:)ってa -> [a] -> [a]で x y = y : xかな…。違った。
ghci> :t flip (:) flip (:) :: [a] -> a -> [a]
引数の時点でリストが先に来ることになってるのか。そうか、reverseの実装だとアキュムレータのリストが先に来るからこれでいいんだ。リストを第一引数にとって、要素を第二引数にとってくっつけて返す…。[a] : aみたいになるのかな。できるのかこれ。そもそも(:)の定義がわからない。
"The Haskell 98 Report: Standard Prelude" http://www.sampou.org/haskell/report-revised-j/standard-prelude.htm
うーん分からん。後回しにしよう。と思ったけどいいのか、先にリストを取るだけで、関数の中身自体はa:[a]のはずだ。受け取った引数を逆にして適用するんだから、初めから引数が逆になってれば、関数の定義は元のままだ。flipは引数を逆にして適用するというより、逆の型の引数をうけとるのかな。
filterやmapみたいなリストを構築するような関数はfoldrの方が相性がいい。:と++の性能の違いがあるから。
lastの実装すごい。リストの中身を片っ端からアキュムレータに入れ替えていくのか。結構ゴリゴリしてるのね。
foldrの無限リストの畳み込み
foldrは右から式を評価するけど、引数の調査（というか適用する関数のパターンマッチ。次の引数を評価しないパターンにマッチするとそこで止まる）自体は左から見るのか。foldlは一回リストを全部展開してから評価しようとするから無限リストが渡されると展開しきれなくなるっぽい。
scanとfold
scanを見るとfoldで何が起こってるのかわかりやすい。scanlは最終結果が最終要素に、scanrは最初の要素に格納される。
sqrtSumsにDefaulting警告が出るので型注釈を書き足した。
sqrtSums :: Int sqrtSums = length (takeWhile (<1000) (scanl1 (+) (map sqrt ([1..] :: [Double])))) + 1
これも順に何が起こってるのか見てみる。
map sqrt ([1..] :: [Double]) （無限リスト） ghci> scanl1 (+) (map sqrt ([1..] :: [Double])) （無限リスト） ghci> takeWhile (<1000) (scanl1 (+) (map sqrt ([1..] :: [Double]))) [1.0,2.414213562373095,4.146264369941973,（略）
これって、一回scal1が適用されるたびに、takeWhileの条件を調べてるんだよな。じゃないと止まらないから。不思議なのは、scanl1した結果に対してtakeWhileの条件付けしてるけど、scanl1はリストを返すんじゃなかったっけ……。ああ違う、takeWhileはリストの要素を、条件に合わなくなるまで取得していくんだった。この場合は、1000より小さい限り順に取得していくと。無限リストだけど遅延評価だから、多分takeWhileの条件に一致するかどうか調べる時に、リストの中身を評価・生成してるんじゃないかと思う。
$
なんか関数定義の括弧が減って見やすくなる。可読性落ちるんじゃないのと思ったけど、順にかたまりを見ていけばいいだけだから、そんなことなかった。後、関数を引数に取る関数を使う時に、関数じゃない値を関数として渡せる。例の($ 3)は関数を引数にとって、3をその関数に適用する関数。本に載ってる関数のリストに対するmapの例は、そのままじゃ3を適用できないんだな。
ghci> negate . (*3) $ 3 -9
なんか$の方が自然な気がしてきた。
関数合成
簡潔に書こうぜ祭り。
関数合成は右結合の意味がわかってなかったけど、関数は右から引数を受け取るから、右結合なら、f.g.h x はf(g (h x)になって、順に適用できるってことか。これが左結合だったら ((f)g) h) xとかわけわからんことになる。
ラムダ式が関数合成の結果に見えるって発想はなかった。確かに。
こういうのって右から見て行かないと何に対してどういう処理をしてるかわからない。
ポイントフリースタイル
ポイントって関数合成の . かとおもいきや、一時変数のことらしい。カリー化で引数省略とからしい。
結構読めるようになってきた。
