Hatena::Grouphaskell

猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 このページをアンテナに追加 RSSフィード

2011-05-08

第7章 高階関数 #2

22:39 | 第7章 高階関数 #2 - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

リスト処理

標準ライブラリPreludeに含まれるリスト処理高階関数

  • map :: (a -> b) -> [a] -> [b]
  • filter :: (a -> Bool) -> [a] -> [a]
  • all :: (a -> Bool) -> [a] -> Bool
  • any :: (a -> Bool) -> [a] -> Bool
  • takeWhile :: (a -> Bool) -> [a] -> [a]
  • dropWhile :: (a -> Bool) -> [a] -> [a]

LINQだとmapがSelectでfilterがWhereだけど、後は同名のメソッドがある。

畳込関数 foldr

来ましたfoldr。定義を写経してみる。

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x : xs) = f x (foldr f v xs)

再帰定義を見ると簡潔だし、無限リスト適用できそうなのも理解できる。ただし

の両方が必要になる(でないと結局foldrは終わらない)。

では、foldrを使って定義したライブラリ関数を写経しよう。

sum     = foldr (+) 0
product = foldr (*) 1
or      = foldr (||) False
and     = foldr (&&) True
length  = foldr (\_ n -> 1 + n) 0
reverse = foldr (\x xs -> xs ++ [x]) []
(++) xs ys  = foldr (:) ys xs

畳込関数 foldl

こっちはLINQにあるけれども、やはり定義を写経。

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x : xs) = foldl f (f v x) xs

ふーむ。定義だけ見ると分かったような分からんような。ただ、無限リスト適用すると、fがどんな性質を持っていようが再帰が終わらないことはわかる。

foldrとfoldlの型を並べてみる。(型変数を揃えておく)

foldr :: (a -> b -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> [a] -> b

というわけで、第1引数の関数が右結合左結合かというのがなんとなく分かった気がする。

上と同じライブラリ関数をfoldlで定義すると。

sum     = foldl (+) 0
product = foldl (*) 1
or      = foldl (||) False
and     = foldl (&&) True
length  = foldl (\n _ -> n + 1) 0
reverse = foldl (\xs x -> x : xs) []
-- 教科書の (++) の定義は意味不明。(xs++)を++で定義している。
-- foldlだけでは定義できなくて、foldrが必要ってこと?

続きはまた明日以降。

第7章 高階関数 #1

21:29 | 第7章 高階関数 #1 - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

map/filter/foldr/foldlを例にした説明。

このうち、foldr以外はLINQにもある。mapはSelect、filterはWhere、foldlはAggregate。だから大体問題ないんだけど、foldrを理解するのにちょっと時間がかかった。

教科書にはまだ書いてなかったんだけど、どうやらfoldrは無限リストを扱えるようなのだ。

まじ?どうやって?なんでfoldlではだめなの?

ということでいろいろ調べながら、C#でfoldrを実装してみた。

C#でfoldr - 平々毎々(アーカイブ)

これで少し納得がいった。foldrで無限リストを扱うには遅延評価が必要だと。

では教科書に戻る。