Arantium Maestum

プログラミング、囲碁、読書の話題

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と一致する。