練習問題 4.3.11

以下のリスト内包表記をコンビネータを用いたスタイルに変換せよ.

[(x,y) | x <- [1 .. n], odd x, y <- [1 .. n]]
[(x,y) | x <- [1 .. n], y <- [1 .. n], odd x]
この2つは等しいか.2つの式の評価コストを比較せよ.



[(x,y) | x <- [1..n], odd x, y <- [1..n]]
    [(x,y) | x <- [1..n], odd x, y <- [1..n]]
=       { 生成規則 }
    concat (map f [1..n]) 
      where f x = [(x,y) | odd x, y <- [1..n]]
=       { ガード規則 }
    concat (map f [1..n]) 
      where f x = if odd x then [(x,y) | y <- [1..n]] else []
=       { 生成規則 }
    concat (map f [1..n]) 
      where f x = if odd x then concat (map g [1..n]) else []
                    where g y = (x,y)
[(x,y) | x <- [1..n],  y <- [1..n], odd x]
    [(x,y) | x <- [1..n],  y <- [1..n], odd x]
=       { 生成規則 }
    concat (map f xs)
      where f x = [ (x,y) | y <- [1 .. n], odd x ]
=       { 生成規則 }
    concat (map f [1..n])
      where f x = concat (map g [1..n]) 
                    where g y = [(x,y) | odd x]
=       { ガード規則 }
    concat (map f [1..n])
      where f x = concat (map g [1..n])
                    where g y = if odd x then [(x,y)] else []

前者では odd x の検査が n 回,後者では n^2 回である.