2008年11月3日月曜日

Haskell で map のネスト

map というとリスト操作の代表格。これがネストすると途端にわかりにくくなるので練習。(@_@;)

その前に型を確認。第1引数に「引数を1つとる関数」、第2引数に「リスト」。

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

曲者は第1引数。未だなんとなく雰囲気と直観とコンパイラに怒られるのを繰り返し、動いた後で「あぁ~、そういうことかぁ」と遅ればせながら理解している。 ^^; 特にここを自分で作成した関数にすると、「ん?あれ?何を書けばいいだっけ?」と思うことがしばしば。

 

ネストなし

まずは基本から。リストの要素を 2 倍にするには、

xs = [1..5]

main = do
  print $ map (\x -> x*2) xs
  print $ map (* 2) xs

無名関数と、二項演算子の部分適用であるセクションを使った。(cf. Haskell のセクションと中置記法) 念のためそれぞれの型を確認しておくと、

Prelude> :t \x -> x*2
\x -> x*2 :: (Num a) => a -> a
Prelude> :t (* 2)
(* 2) :: (Num a) => a –> a

map の第1引数には「引数を1つ取る関数」を与えればいいので、上記の関数はそれに適合しているのがわかる。

 

リストを与えると要素を 2 倍にする関数を定義するなら、

map1a xs = map (* 2) xs
map1b = map (* 2)

map1a は引数にリストを取る関数。 map1b は map 関数に第一引数を部分適用した関数。

 

リスト内包表記

リスト内包表記で書くと、

  print [x*2 | x <-xs]

はじめこれを書くとき、後ろから前へと書いていた。つまり、xs を最初に書き、最後に要素に対する操作 x*2 を書く。しかし、それだと「何か書きにくいなぁ」と思い、試しに前から書いてみたら、以下のように頭の中で唱えればわりとスムーズに書けた。

  1. 要素 x を 2 倍したい : x*2
  2. 要素 x は xs に由来する : x <- xs

実は Python でリスト内包表記を書くときも、最初に x for x in L と外観を書いてから、x * 2 と書いていた。そうでないと、何かイメージしにくかったというか…。英語だと自然に読めると、どこかで読んだ覚えがあったのだけれど。 ^^;

 

map のネスト

次に、ネストしたリストに map を適用してみる。例えば、以下のようなリストがあるとする。

xss = [[1..5],[10..15],[100..105]]

この要素の中身を 2 倍するには、map を 2 回適用する。一つは要素を 2 倍するための map 、もう一つは要素を棚卸しする map 。

  print $ map (\xs -> map (* 2) xs) xss
  print $ map (map (* 2)) xss

先ほどと同じように、無名関数と部分適用を使った。無名関数の中で要素を束縛する変数 xs は、xss から棚卸ししたことがわかるように xss から s を一つとったもの。これを目安にネストの具合を想像できる。

同じく関数の型について調べると、

Prelude> :t \xs -> map (* 2) xs
\xs -> map (* 2) xs :: (Num a) => [a] -> [a]
Prelude> :t \xs -> map (* 2) xs
\xs -> map (* 2) xs :: (Num a) => [a] -> [a]

今度は、第1引数がリストになっているけれど、全体では引数を一つ取る関数であることがわかる。これは map の第1引数としての要件を満している。

 

関数にすると、

map2a xss = map (map (* 2)) xss
map2b = map (map (* 2))

 

where 節

( ) があってごちゃごちゃしているので、( ) 内を where 節に書くと、

map2c xss = map map' xss
    where map' xs = map (* 2) xs

map2d = map map'
    where map' = map (* 2)

徐々に、見慣れないとすぐに読めなくなってきた。(@_@;) ここでは、where 節に map’ という名前の関数を定義。

… うーん、何がわかりにくくさせる原因だろう? 考えてみると、先ほどのように無名関数を与えた場合は、map に与えたリストの要素を束縛するための変数が明示されてるので、どんな中身に何を適用しているかがわかりすい。それに対して、上記の map’ はどうだろう? まず見た瞬間、「ん? map’ の対象は何で、どこに何を入れるのだろうか…」と。

これを何も考えずにスラスラと書けるようになるまでは、関数の型を見て考えるのがいいかも。自分の場合、はじめここまで書いていて、ピタッと手が止った。

map2c xss = map map' xss
    where map' …

「あれれ? map’ って何を対象にしているだっけ?」と。

map 関数の型を再掲すると、

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

今回は [b] に相当するのが xss で [[Integer]]。これを GHCi で map に部分適用してみる。(cf. Haskell の部分適用 (2))

*Main> let xss = [[1..5],[10..15],[100..105]]
*Main> :t flip map xss
flip map xss :: ([Integer] -> b) -> [b]

もしくは、

*Main> :t \f -> map f xss
\f -> map f xss :: ([Integer] -> b) -> [b]

これで map’ 関数の型が見えてきた。 [b] は [[Integer]] となるはずなので、b は [Integer] 。よってこれを見ながら、

map2c xss = map map' xss
    where map' xs = map (* 2) xs

…と、そこまで考えなくても、最初の map は「棚卸し用の mapで、与えられたリストの要素を map’ 関数に渡していると想像すればいいか… ^^;

 

部分適用を用いると、引数が消えよりシンプルに、

map2d = map map'
    where map' = map (* 2)

しかし、慣れないと見た瞬間何かわからない。 (@_@;)

 

リスト内包表記

リスト内包表記で書くと、

  print $  [[x*2 | x <- xs]| xs <- xss]

これも先ほどと同じように、

  • 要素 x を 2 倍したい
  • x は xs に由来する
  • xs は xss に由来する

と考えながら書くと、素直に先頭から書いていくことができた。

 

ネストのネスト

せっかくなので、もう一段ネストしたリストも書いてみる。

xsss = [[[1..3],[4..6]],[[10..13]],[[100..103],[104..106],[107..110]]]

を対象にすると、

  print $ map (\xss -> map (\xs -> map (* 2) xs) xss) xsss
  print $ map (map (map (* 2))) xsss

無名関数を使う方は大変なことに… (@_@;)

 

関数にすると、

map3a xsss = map (map (map (* 2))) xsss
map3b = map (map (map (* 2)))

 

where 節

先ほどと同じように where 節を使うと、

map3c xsss = map map' xsss
    where map'

ここで GHCi で map’ 関数の型を調べてみると、

*Main> let xsss = [[[1..3],[4..6]],[[10..13]],[[100..103],[104..106],[107..110]]]
*Main> :t flip map xsss
flip map xsss :: ([[Integer]] -> b) -> [b]

または、

*Main> :t \f -> map f xsss
\f -> map f xsss :: ([[Integer]] -> b) -> [b]

[b] は [[[Integer]]] となる予定なので、b は [[Integer]]。

これを更に棚卸して最終的に、

map3c xsss = map map' xsss
    where map' xss = map map'' xss
              where map'' xs = map (* 2) xs

map3d = map map'
    where map' = map map''
              where map'' = map (* 2)

 

リスト内包表記

リスト内包表記で書くなら、

  print $ [[[x*2 | x <- xs] | xs <- xss] | xss <- xsss]