Thinking Functionally with Haskell勉強メモ: 第4章1: List Comprehensionの定義
Haskellでは
Prelude> [1..5] [1,2,3,4,5] Prelude> [(+1) x | x <- [1..5]] [2,3,4,5,6]
のように[a..b]
と[f x | x <- xs]
といった簡単にリストを作成できる記法がサポートされている。
後者は特に便利で
Prelude> [x*y | x <- [1..10], x `mod` 2 == 0, y <- [10..20], y `mod` 3 == 0] [24,30,36,48,60,72,72,90,108,96,120,144,120,150,180]
のようにFilter的な挙動や複数のリストのCartesian Product的なことができる。
map
/filter
/concat
はこのList Comprehension記法で簡単に定義できる:
map f xs = [f x | x <- xs] filter p xs = [x | x <- xs, p x] concat xss = [x | xs <- xss, x <- xs]
しかし実際にはList Comprehensionの方が以下のルールに従ってmap``filter``concat
での定義に変換される:
[e |True] = [e] [e | q] = [e | q, True] [e | b, Q] = if b then [e | Q] else [] [e | p <- xs, Q] = let ok p = [e | Q] ok _ = [] in concat (map ok xs)
以上のルールは正式な定義ではなく、単にHaskell内での変換則を作者が記述したものなのだろうか?少なくともghciが受け付けるコードではない。
[f x | x <- xs]
を変換してみると
[f x | x <- xs] = [f x | x <- xs, True] -- 2nd rule = let ok x = [f x | True] ok _ = [] in concat (map ok xs) -- 4th rule = let ok x = [f x] -- 1st rule ok _ = [] in concat (map ok xs) = concat (map (\x -> [f x]) xs) -- substitute ok
となって確かにmap
と等しいようだ。(ただ、2段目でrule 4ではなくrule 3でもマッチするようだが・・・)
同じく[x | x <- xs, p x]
も:
[x | x <- xs, p x] = let ok x = [x | p x] ok _ = [] in concat (map ok xs) -- 4th rule = let ok x = [x | p x, True] -- 2nd rule ok _ = [] in concat (map ok xs) = let ok x = if p x then [x | True] else [] -- 3rd rule ok _ = [] in concat (map ok xs) = let ok x = if p x then [x] else [] -- 1st rule ok _ = [] in concat (map ok xs) = concat (map (\x -> if p x then [x] else []) xs) -- substitute ok
でfilter
と一致する。