top page > computer > haskell > web_lecture > for_programmer > list_comprehensions_trans.html
更新日:
文責: 重城良国

構文: リスト内包表記の変形

(工事中 0%)

はじめに

入れ子になったリスト内包表記を変形して平坦にすることを考える。

変形

以下のような変形が可能であることを示す。

[ 結果 | ..., (x, y) <- [ (x, y) | x <- 式1, y <- 式2 ], ... ] => [ 結果 | ..., x <- 式1, y <- 式2, ... ]

脱糖

(脱糖のしかたを再掲する)

[ rst | var1 <- exp1, var2 <- exp2, ..., varN <- expN ]

は以下のように脱糖される。

(`concatMap` exp1) $ \var1 ->
(`concatMap` exp2) $ \var2 ->
...
(`concatMap` expN) $ \varN ->
[rst]

bind :: [a] -> (a -> [b]) -> [b]
bind = flip concatMap

とすると

exp1 `bind` \var1 ->
exp2 `bind` \var2 ->
...
expN `bind` \varN ->
[rst]

となる。

わける

(内包表記の前後をわけるやりかたを説明する)

[ rst | var1 <- exp1, var2 <- exp2, ..., varK <- expK, varL <- expL, ..., varN <- expN ]

上が下と同じ値になることを示す。

[ rst | (var1, var2, ..., varK) <- [ (var1, var2, ..., varK) | var1 <- exp1, var2 <- exp2, ..., varK <- expK ], varL <- expL, ..., varN <- expN ]

平坦化

(以下の式が成り立つことを示す)

[ r | (x, y) <- [ (x, y) | x <- exp1, y <- exp2 ], r <- exp3 ]
<=> [ r | x <- exp1, y <- exp1, r <- exp3 ]

くっつける

(「わけかた」から「平坦化」の式の前後に式を追加して求める変形を示す)

メモ

concatMap :: (a -> [b]) -> [a] -> [b]

cm = flip concatMap

[a] `cm` k = k a
m `cm` (: []) = m
m `cm` (\x -> k x `cm` h) = (m `cm` k) `cm` h

do記法っぽくモナド則を表現してみよう。

m >>= (\x ->
k x -> \y ->
h y)

(m >>= \x ->
k x) >> \y ->
h y

たとえば以下のような場合どうなるか。

m >>= (\x ->
k x >>= \y ->
h x y)

[ r | x <- m, y <- k x, r <- h x y ]

(m >>= \x ->
k x >>= \y -> return (x, y)) >> \(x, y) ->
h x y

[ r | (x, y) <- [ (x, y) | x <- m, y <- k x ], r <- h x y ]

(m >>= \x -> k x >>= \y -> return (x, y)) >> \(x, y) -> h x y
=>

m >>= (\x -> k x >>= \y -> h x y)

「わける」の示しかた

まずは2の場合から3の場合を導いてみる。

[ (x, y, z) | x <- u, y <- v, z <- w ]
<=> [ (x, y, z) | (x, y) <- [ (x, y) | x <- u, y <- v ], z <- w ]

[ (x, y, z, a) | x <- u, y <- v, z <- w, a <- t ]
<=> [ (x, y, z, a) | (x, y) <- [ (x, y) | x <- u, y <- v ], z <- w, a <- t ]
<=> [ (x, y, z, a) | ((x, y), z) <- [ ((x, y), z) | (x, y) <- [ (x, y) | x <- u, y <- v ], z <- w ], a <- t ]
<=> [ (x, y, z, a) | (x, y, z) <- [ (x, y, z) | (x, y) <- [ (x, y) | x <- u, y <- v ], z <- w ], a <- t ]
<=> [ (x, y, z, a) | (x, y, z) <- [ (x, y, z) | x <- u, y <- v, z <- w ], a <- t ]

前処理

前処理として以下をやっておくといいかも。

[ rst | var1 <- exp1, var2 <- exp2, ..., varN <- expN ]

map (\(var1, var2, ..., varN) -> rst) [ (var1, var2, ..., varN) | var1 <- exp1, var2 <- exp2, ..., varN <- expN ]

「構文: リスト内包表記(2)」へもどる 「パーサ: はじめに」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics