お気楽 Haskell プログラミング入門

高階関数 (2)

関数型言語の場合、リスト操作関数の多くは高階関数として定義されています。今回はよく使われる高階関数として、マッピング、フィルター、畳み込み (縮約) について説明します。

●マッピング

まず最初に、リストの要素に関数 f を適用して、その結果をリストに格納して返す関数を作ってみましょう。このような操作を「マッピング (写像)」といいます。次のリストを見てください。

リスト : マッピング

map' :: (a -> b) -> [a] -> [b]
map' _ [] = []
map' f (x:xs) = f x : map' f xs

Haskell にはマッピングを行う関数 map が定義されているので、ここでは関数名を map' としました。プログラムは簡単です。パターンマッチングで引数のリストを先頭の要素 x と残りのリスト xs に分解します。そして、x に関数 f を適用した結果と map' f xs の結果をコンス演算子 : で結合します。引数のリストが空リストの場合が再帰呼び出しの停止条件になります。

ここで map' の型に注目してください。第 1 引数が関数型 a -> b で第 2 引数がリスト [a] になります。関数 f はリストの要素を受け取るので、関数 f の引数の型とリストの型は一致します。これを型変数 a で表しています。同様に、関数 f の返り値の型と map' の返り値のリストの型は一致します。これを型変数 b で表しています。このように、map' は多相型関数として定義されます。

簡単な実行例を示します。

*Main> map' (*2) [1,2,3,4,5]
[2,4,6,8,10]
*Main> map' (+10) [1,2,3,4,5]
[11,12,13,14,15]

マップ関数を使うと前回作成した sum_of を簡単に定義することができます。

*Main> sum_of f n m = sum (map f [n .. m])
*Main> sum_of id 1 10
55
*Main> sum_of id 1 100
5050
*Main> sum_of (^2) 1 10
385
*Main> sum_of (^2) 1 100
338350
*Main> sum_of (^3) 1 10
3025
*Main> sum_of (^3) 1 100
25502500

[n .. m] で n 以上 m 以下の数列 (リスト) を生成し、map でその要素に関数 f を適用します。最後に、map で生成されたリストの要素の総和を sum で求めればいいわけです。とても簡単ですね。

●フィルター

「フィルター (filter)」はリストの要素に関数を適用し、関数が真を返す要素をリストに格納して返す関数です。真偽値を返す関数のことを「述語 (predicate)」といいます。ここでは簡単な例題として、述語が真を返す要素を削除する関数 remove_if を作ってみましょう。関数名は Common Lisp から拝借しました。

リスト : 要素の削除

remove_if :: (a -> Bool) -> [a] -> [a]
remove_if _ [] = []
remove_if p (x:xs)
  | p x       = remove_if p xs
  | otherwise = x : remove_if p xs

map' と同様に remove_if も簡単です。p x が真ならば x をリストに加えません。偽ならば x をリストに加えるだけです。remove_if の型ですが、述語 p は if の条件式で使われているので、型は a -> Bool となります。もちろん、remove_if も多相型関数として定義されます。簡単な実行例を示します。

*Main> remove_if even [1,2,3,4,5,6,7,8]
[1,3,5,7]
*Main> remove_if (== "abc") ["abcd", "abc", "ab", "a"]
["abcd","ab","a"]

最初の例では偶数の要素が削除されます。次の例は文字列 "abc" が削除されます。

もちろん、フィルターも簡単に定義することができます。remove_if とは逆に、述語が真を返すとき要素をリストに追加し、偽を返すときはリストに加えません。なお、Haskell には同様の動作を行う関数 filter が定義されているので、ここでは関数名を filter' としました。

リスト : フィルター

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x:xs)
  | p x       = x : filter' p xs
  | otherwise = filter' p xs

簡単な実行例を示しましょう。

*Main> filter' even [1,2,3,4,5,6,7,8]
[2,4,6,8]
*Main> filter' (== "abc") ["abcd", "abc", "ab", "a"]
["abc"]
*Main> filter' (/= "abc") ["abcd", "abc", "ab", "a"]
["abcd","ab","a"]

●畳み込み

2 つの引数を取る関数 f とリストを引数に受け取る関数 reduce を考えます。reduce はリストの各要素に対して関数 f を下図のように適用します。

(1) [a1, a2, a3, a4, a5]
    => f( f( f( f( a1, a2 ), a3 ), a4 ), a5 )

(2) [a1, a2, a3, a4, a5]
    => f( a1, f( a2, f( a3, f( a4, a5 ) ) ) )


        図 : 関数 reduce の動作

関数 f を適用する順番で 2 通りの方法があります。図 (1) はリストの先頭から f を適用し、図 (2) はリストの後ろから f を適用します。たとえば、関数 f が単純な加算関数とすると、reduce の結果はどちらの場合もリストの要素の和になります。

f(x, y) = x + y の場合
reduce => a1 + a2 + a3 + a4 + a5

このように、reduce はリストのすべての要素を関数 f を用いて結合します。このような操作を「縮約」とか「畳み込み」といいます。また、reduce の引数に初期値 g を指定することがあります。この場合、reduce は下図に示す動作になります。

(1) [a1, a2, a3, a4, a5]
    => f( f( f( f( f( g, a1 ), a2 ), a3 ), a4 ), a5 )

(2) [a1, a2, a3, a4, a5]
    => f( a1, f( a2, f( a3, f( a4, f( a5, g ) ) ) ) )


        図 : reduce の動作 (2)

ここでは簡単な例題として、上図 (1) の動作を行う関数 fold_left と、(2) の動作を行う関数 fold_right を作ってみましょう。なお、Haskell には同様の動作を行う関数 foldl と foldr があります。

プログラムは次のようになります。

リスト : 畳み込み

fold_left :: (a -> b -> a) -> a -> [b] -> a
fold_left _ a []     = a
fold_left f a (x:xs) = fold_left f (f a x) xs

fold_right :: (a -> b -> b) -> b -> [a] -> b
fold_right _ a []     = a
fold_right f a (x:xs) = f x (fold_right f a xs)

第 1 引数 f が適用する関数、第 2 引数 a が初期値、第 3 引数がリストです。最初の節は再帰呼び出しの停止条件ですが、fold_left (fold_right) に空リストが与えられた場合にも対応します。この場合は初期値 a を返します。次の節でリストの要素を取り出して関数 f を呼び出します。

たとえば、リストが [1, 2, 3] で a が 0 とします。最初は f(0, 1) が実行され、その返り値が fold_left の第 2 引数に渡されます。次は f(a, 2) が実行されますが、これは f(f(0, 1), 2) と同じことです。そして、その結果が fold_left の第 2 引数になります。最後に f(a, 3) が実行されますが、これは f(f(f(0, 1), 2), 3) となり、図 (1) と同じ動作になります。

fold_left の場合、リストの要素が関数 f の第 2 引数になり、第 1 引数にはこれまでの処理結果が渡されます。これに対し、fold_right の場合は逆になり、関数 f の第 1 引数にリストの要素が渡されて、これまでの処理結果は第 2 引数に渡されます。これで図 (2) の動作を実現することができます。

ここで型を見てみましょう。fold_left と fold_right の返り値は初期値 a の型と同じになります。つまり、リストの要素と同じ型である必要はありません。そして、渡される関数の型にも注目してください。fold_left の場合、関数の第 1 引数と初期値の型が同じです。第 1 引数に今までの処理結果が渡されて、第 2 引数にリストの要素が渡されることがわかります。これに対し、fold_right は逆になっていることに注意してください。

簡単な実行例を示します。

*Main> fold_left (+) 0 [1,2,3,4,5]
15
*Main> fold_right (+) 0 [1,2,3,4,5]
15

どちらの例もリストの要素の総和を求めています。畳み込みを使うと、関数 sum は次のように定義することができます。

リスト : 要素の総和を求める

sum' :: Num a => [a] -> a
sum' xs = fold_left (+) 0 xs

●畳み込みの使用例

このほかにも、畳み込みと 2 引数の関数を組み合わせると、いろいろな関数を実現することができます。最初に length の例を示します。

*Main> let length' xs = fold_left (\a _ -> a + 1) 0 xs
*Main> length' []
0
*Main> length' [1,2,3,4,5]
5

fold_left で length を実現する場合、初期値を 0 にしてラムダ式の第 1 引数 a を +1 することで実現できます。

次に map の例を示します。

*Main> let map' f xs = fold_right (\x a -> f x : a) [] xs
*Main> map' (^2) [1,2,3,4,5]
[1,4,9,16,25]

map は fold_rigth を使うと簡単です。初期値を [ ] にしてラムダ式の第 1 引数に関数 f を適用した結果を第 2 引数のリストに追加するだけです。

次に filter の例を示します。

*Main> let filter' p xs = fold_right (\x a -> if p x then x:a else a) [] xs
*Main> filter' even [1,2,3,4,5,6,7,8]
[2,4,6,8]
*Main> filter' odd [1,2,3,4,5,6,7,8]
[1,3,5,7]

filter の場合も初期値を [ ] にして、ラムダ式の第 1 引数が条件を満たしていれば第 2 引数のリストに追加します。

最後に述語が真となる要素の個数を求めてみましょう。これは Common Lisp の関数 count-if と同じです。

*Main> let count_if p xs = fold_left (\a x -> if p x then a + 1 else a) 0 xs
*Main> count_if even [1,2,3,4,5,6,7]
3
*Main> count_if odd [1,2,3,4,5,6,7]
4

このように、畳み込みを使っていろいろな処理を実現することができます。

●リスト内包表記

Hakell でリストを操作する場合、高階関数だけではなく「リスト内包表記 (List Comprehensions)」を使うことができます。基本的な構文を次に示します。

[式 | パターン <- 式, 条件式]

角カッコ [ ] の最初にリストの要素を生成する式を記述します。次に縦線 ( | ) で区切ったあと、"パターン <- 式" を記述します。これを「生成器」と呼ぶことにします。式の値はリストでなければなりません。式はリストをそのまま指定してもかまいません。<- はリストの先頭から順番に要素を取り出し、パターンとマッチングを行います。また、カンマで区切ったあと、条件式を指定することができます。

簡単な例を示しましょう。

Prelude> [x * x | x <- [1 .. 10]]
[1,4,9,16,25,36,49,64,81,100]
Prelude> [x * x | x <- [1 .. 10], even x]
[4,16,36,64,100]
Prelude> [x * x | x <- [1 .. 10], odd x]
[1,9,25,49,81]

最初の例は要素を 2 乗したリストを生成します。次の例は、偶数の要素を取り出して 2 乗します。最後の例は奇数の要素を取り出して 2 乗します。これらの動作は map や filter と同じです。

リスト内包表記は複数の生成器を指定することもできます。次の例を見てください。

Prelude> [(x,y) | x <- [1,2,3], y <- [4,5,6]]
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

最初に、x が 1 とマッチングし、次に y がリスト [4, 5, 6] の要素とマッチングして、タプル (1,4), (1,5), (1,6) が生成され生ます。次に、x の値が 2 に束縛されてから再度 y と [4, 5, 6] のマッチングが動作するので、タプル (2,4), (2,5), (2,6) が生成されます。最後に、x が 3 に束縛されてタプル (3,4), (3,5), (3,6) が生成されます。

また、それぞれの生成器のあとに条件式を設定することもできます。簡単な例を示します。

Prelude> [(x, y) | x <- [1..10], even x, y <- [1..10], odd y]
[(2,1),(2,3),(2,5),(2,7),(2,9),(4,1),(4,3),(4,5),(4,7),(4,9),(6,1),(6,3),(6,5),
 (6,7),(6,9),(8,1),(8,3),(8,5),(8,7),(8,9),(10,1),(10,3),(10,5),(10,7),(10,9)]

タプルの第 1 要素 x は偶数、第 2 要素 y は奇数になります。

それでは簡単な例題として、リスト内包表記を使ってクイックソートを書き直してみましょう。

リスト : クイックソート

quick_sort' :: Ord a => [a] -> [a]
quick_sort' [] = []
quick_sort' (x:xs) = quick_sort' [y | y <- xs, y < x]
                  ++ [x]
                  ++ quick_sort' [y | y <- xs, y >= x]

引数のリストが空リストであれば空リストを返します。そうでなければ、リストの先頭要素 x を枢軸として、リスト内包表記で x より小さい要素と x 以上の要素に分けます。あとは quick_sort を再帰呼び出しして、その結果を [x] をはさんで演算子 ++ で連結するだけです。ただし、リスト xs を二分割するとき、xs を 2 回走査することに注意してください。

もうひとつ簡単な例題として、リストを平坦化する関数 flatten を作ってみましょう。なお、Haskell には同じ働きをする関数 concat が用意されています。簡単な動作例を示します。

*Main> flatten [[1,2,3],[4,5,6],[7,8,9]]
[1,2,3,4,5,6,7,8,9]
*Main> flatten [[1,2,3],[],[4,5,6],[],[7,8,9]]
[1,2,3,4,5,6,7,8,9]

プログラムは次のようになります。

リスト : リストの平坦化

flatten :: [[a]] -> [a]
flatten [] = []
flatten (x:xs) = x ++ flatten xs

-- リスト内包表記
flatten' :: [[a]] -> [a]
flatten' xss = [x | xs <- xss, x <- xs]

flatten はリストの先頭要素 x を取り出して、x と次の要素を演算子 ++ で結合すればいいわけです。リスト内包表記を使うともっと簡単になります。リスト xss から要素 xs を取り出し、xs からさらに要素 x を取り出します。あとは、x をリストに格納して返すだけです。

●問題

次の関数を定義してください。

関数 fn にリストを渡すマップ関数 maplist fn xs
2 つのリスト xs, ys の要素に対して関数 fn を適用し、その結果をリストに格納して返すマップ関数 zipWith' fn xs ys

リストの長さが異なる場合、短いほうのリストに合わせるものとする
なお、Haskell のモジュール Data.List には同様の関数 zipWith がある

述語 pred を満たす要素の個数を数える関数 count_if pred xs
- 畳み込みを使わずに再帰で定義してください
リスト xs を先頭から畳み込むとき、計算途中の累積値をリストに格納して返す scan_left fn a xs
リスト xs を末尾から畳み込むとき、計算途中の累積値をリストに格納して返す scan_right fn a xs

Haskell のモジュール Data.List には、同様の関数 scanl と scanr がある

●解答

リスト : 解答例 (q05.hs)

maplist :: ([a] -> b) -> [a] -> [b]
maplist _ [] = []
maplist fn xs@(_:ys) = fn xs : maplist fn ys

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' fn (x:xs) (y:ys) = fn x y : zipWith' fn xs ys

count_if :: (a -> Bool) -> [a] -> Int
count_if _ [] = 0
count_if pred (x:xs) = (if pred x then 1 else 0) + count_if pred xs

scan_left :: (a -> b -> a) -> a -> [b] -> [a]
scan_left _ a [] = [a]
scan_left fn a (x:xs) = a : scan_left fn (fn a x) xs

scan_right :: (a -> b -> b) -> b -> [a] -> [b]
scan_right _ a [] = [a]
scan_right fn a (x:xs) =
  let
    ys = scan_right fn a xs
  in
    fn x (head ys) : ys

Prelude> :l q05.hs
[1 of 1] Compiling Main             ( q05.hs, interpreted )
Ok, one module loaded.

*Main> maplist id [10,20,30,40,50]
[[10,20,30,40,50],[20,30,40,50],[30,40,50],[40,50],[50]]
*Main> maplist length [1,2,3,4,5]
[5,4,3,2,1]

*Main> zipWith' (+) [1,2,3,4,5] [6,7,8,9,10]
[7,9,11,13,15]
*Main> zipWith' (*) [1,2,3,4,5] [6,7,8,9,10]
[6,14,24,36,50]

*Main> count_if even [1 .. 11]
5
*Main> count_if odd [1 .. 11]
6
*Main> count_if (<4) [1 .. 11]
3
*Main> count_if (>4) [1 .. 11]
7

*Main> scan_left (+) 0 [1 .. 10]
[0,1,3,6,10,15,21,28,36,45,55]
*Main> scan_left (*) 1 [1 .. 10]
[1,1,2,6,24,120,720,5040,40320,362880,3628800]

*Main> scan_right (+) 0 [1 .. 10]
[55,54,52,49,45,40,34,27,19,10,0]
*Main> scan_right (*) 1 [1 .. 10]
[3628800,3628800,1814400,604800,151200,30240,5040,720,90,10,1]

●scan_left と scan_right

scan_left はリストの最後の要素が最終の累積値になります。xs が空リストのとき、累積変数 a の値をリストに格納して返します。そうでなければ、scan_left を再帰呼び出しして、その返り値に累積変数 a の値を追加して返します。scan_left を再帰呼び出しするときは、関数 fn を呼び出して累積変数の値を更新することに注意してください。

scan_right はリストの先頭の要素が最終の累積値、最後の要素が初期値になります。第 3 引数が空リストの場合は [a] を返します。そうでなければ、scan_right を再帰呼び出しします。このとき、累積変数 a の値は更新しません。返り値のリストは変数 ys にセットします。この ys の先頭要素が一つ前の累積値になるので、この値とリストの要素 x を関数 fn に渡して評価します。あとは、fn の返り値を ys の先頭に追加して返せばいいわけです。

初版 2013 年 1 月 20 日
改訂 2021 年 1 月 10 日

レキシカルスコープとクロージャ

変数の有効範囲を表す用語に「スコープ (scope)」があります。この用語を使うと、厳密ではありませんが、変数の有効範囲は「レキシカルスコープ (lexical scope)」と「ダイナミックスコープ (dynamic scope)」の 2 つに分けることができます。伝統的な Lisp はダイナミックスコープですが、現在のプログラミング言語、たとえば、Scheme, Common Lisp, SML/NJ, OCaml, Haskell はレキシカルスコープを採用しています。

●レキシカルスコープ

それでは、レキシカルスコープについて詳しく見てみましょう。引数を無視して変数 x の値を返す関数 foo を定義します。

Prelude> x = 10
Prelude> foo a = x
Prelude> foo 0
10

関数 foo には局所変数 x を定義していないので、foo を実行した場合は大域変数の値を参照します。その結果、返り値は 10 となります。それでは、foo1 という関数から foo を呼び出す場合を考えてみましょう。foo1 には let で局所変数 x を定義します。この場合、foo はどちらの値を返すのでしょうか。実際に試してみましょう。

Prelude> foo1 b = let x = 100 in foo b
Prelude> foo1 0
10

foo1 を実行すると大域変数の値 10 を返しました。このように、foo1 で定義した局所変数 x は、foo から参照することはできません。次の図を見てください。

上図では変数の有効範囲を枠で表しています。foo1 の let で定義した局所変数 x は、let の枠の中でのみ有効です。もしも、この枠で変数が見つからない場合は、ひとつ外側の枠を調べます。順番に外側の枠を調べていくと、最後には関数定義の枠に行き着きます。ここで変数（引数）が見つからない場合は大域変数を調べます。

関数 foo は関数定義の枠しかありません。そこに変数 x が定義されていないので、大域変数を調べることになるのです。このように、関数 foo から foo1 の枠と let の枠を超えて変数 x にアクセスすることはできないのです。これを「レキシカルスコープ」といいます。レキシカルには文脈上いう意味があり、変数が定義されている構造の範囲内 (枠内) でないと、その変数にアクセスすることはできません。

ところが伝統的な Lisp の場合、foo1 で定義した変数 x は呼び出された関数 foo からアクセスすることができます。これを「ダイナミックスコープ」といいます。foo1 で定義された変数 x は、foo1 の実行が終了するまで存在します。そして、foo1 から呼ばれた関数ならば、どこからでも参照することができるのです。もしも、foo1 をダイナミックスコープの処理系、たとえば Emacs Lisp で実行するならば、foo が返す x の値は 100 になります。

●レキシカルスコープと局所関数

それでは、関数の中で定義された局所関数やラムダ式の場合はどうなるのでしょうか。次の例を見てください。

Prelude> times_element n xs = map (\x -> x * n) xs
Prelude> times_element 10 [1,2,3,4,5,6]
[10,20,30,40,50,60]

ラムダ式の引数は x だけなので、変数 n は大域変数を参照するように思われるかもしれません。ところが、変数 n は関数 times_element の引数 n を参照するのです。これを図に示すと、次のようになります。

ポイントは、ラムダ式が times_element 内で定義されているところです。変数 n は関数の引数として定義されていて、その有効範囲は関数の終わりまでです。ラムダ式はその範囲内に定義されているため、変数 n にアクセスすることができるのです。つまり、関数内で定義されたラムダ式は、そのとき有効な局所変数にアクセスすることができるのです。

これは let で定義された局所的な関数も同じです。times_element は次のように書き換えることができます。

Prelude> times_element n xs = let timesN x = x * n in map timesN xs
Prelude> times_element 10 [1,2,3,4,5,6]
[10,20,30,40,50,60]

局所関数 timesN は times_element 内で定義されているので、timesN から times_element の引数 n を参照することができます。

もちろん、セクションを使っても動作します。

Prelude> times_element n xs = map (*n) xs
Prelude> times_element 10 [1,2,3,4,5,6]
[10,20,30,40,50,60]

Haskell の場合、これが一番簡単ですね。

●クロージャ

Lisp などの関数型言語では、関数を生成する関数を簡単に作ることができます。このとき使われる機能が「クロージャ (closure)」です。クロージャは評価する関数と参照可能な局所変数をまとめたものです。クロージャは関数のように実行することができますが、クロージャを生成するときに参照可能な局所変数を保持するところが異なります。参照可能な局所変数の集合を「環境」と呼ぶことがあります。

Haskell の関数はカリー化できるので、関数を返す関数はとても簡単に作成することができます。また、Haskell は関数型言語なので、当然ですがクロージャも使うことができます。Haskell でクロージャを生成するにはラムダ式を使うか、局所的な関数を定義して、その関数を返します。たとえば、「引数を n 倍する関数」を生成する関数は、ラムダ式を使うと次のようになります。

Prelude> foo n = \x -> x * n
Prelude> :t foo
foo :: Num a => a -> a -> a
Prelude> foo10 = foo 10
Prelude> :t foo10
foo10 :: Num a => a -> a
Prelude> foo10 10
100
Prelude> foo10 20
200
Prelude> foo10 1.25
12.5

Prelude> foo100 = foo 100
Prelude> foo100 10
1000
Prelude> foo100 20
2000
Prelude> foo100 1.25
125.0

Prelude> foo5 = foo 5
Prelude> foo5 10
50
Prelude> foo5 20
100
Prelude> foo5 1.25
6.25

関数 foo は引数を n 倍する関数を生成します。関数 foo の型 Num a => a -> a -> a は a -> (a -> a) を意味しています。これは引数 a を受け取り a -> a という関数を返すことを表しています。変数 foo10 に foo 10 の返り値をセットします。すると、foo10 は引数を 10 倍する関数として使うことができます。同様に、変数 foo5 に foo 5 の返り値をセットすると、foo5 は引数を 5 倍する関数になります。foo5, foo10, foo100 の型は Num a => a -> a になるので、引数が整数でも実数でも動作します。

ラムダ式を生成するとき、評価する関数のほかに、そのとき参照可能な局所変数、つまり「環境」もいっしょに保存されます。この場合、参照可能な局所変数は foo の引数 n です。そして、クロージャを実行するときは、保存されている局所変数を参照することができるのです。

foo 10 を実行して無名関数を生成するとき、定義されている局所変数は n で、その値は 10 ですね。この値がクロージャに保存されているので、foo10 の関数は引数を 10 倍した結果を返します。foo 5 を評価すると n の値は 5 で、それがクロージャに保存されているので、foo5 の関数は引数を 5 倍した結果を返すのです。

また、let で局所的な関数を定義して、その関数を返すとクロージャを生成することができます。let を使った例を示します。

Prelude> foo n = let bar x = x * n in bar
Prelude> foo100 = foo 100
Prelude> foo100 10
1000
Prelude> foo5 = foo 5
Prelude> foo5 10
50

関数 bar を定義して、bar を返します。すると、foo は「引数を n 倍する関数」を生成する関数になります。

もっとも、Haskell では関数をカリー化するだけで同様の関数を作ることができます。

Prelude> foo n x = n * x
Prelude> :t foo
foo :: Num a => a -> a -> a
Prelude> foo100 = foo 100
Prelude> :t foo100
foo100 :: Num a => a -> a
Prelude> foo100 10
1000
Prelude> foo5 = foo 5
Prelude> foo5 10
50

このように、Haskell は関数をカリー化できるので、部分適用により目的の関数を簡単に生成することができます。

●連想リスト

クロージャを理解する場合、環境を「連想リスト (association list : a-list)」で考えるとわかりやすいと思います。ここで簡単に連想リストについて説明します。

連想リストは Lisp でよく用いられるデータ構造で、Haskell ではキーとデータのタプルを要素とするリストで実現することができます。データ型で記述すると [(a, b)] になり、a がキーで b がデータに対応します。

上図の場合、文字列 "a", "b", "c", "d" がキーで、整数 1, 2, 3, 4 がデータとなります。

一般に、関数を呼び出す場合、関数を評価するための環境は空リストです。最初に、引数がこの環境に追加されます。let で定義される局所変数もこの環境に追加されます。もしも、環境に該当する変数が存在しない場合は大域変数を参照します。

たとえば、foo 5 と呼び出すと環境は次のようになります。

foo 5 ==> 環境 : [(n, 5)]

連想リストのキー n が変数名で、その値が 5 です。クロージャを生成するとき、この連想リストを保持すると考えてください。そして、クロージャを評価するときは、保存していた環境を使います。したがって、foo5 11 を評価すると、環境 [(n, 5)] に引数 x の値が追加され、[(x, 11), (n, 5)] になります。この環境で式 n * x を評価するので、5 * 11 = 55 を返すわけです。

関数の評価が終了すると、環境に追加された変数は削除されます。foo5 11 の評価で追加された変数は x なので、(x, 11) が削除され [(n, 5)] になります。このように、クロージャに保存された環境は変化しません。

ただし、Common Lisp や Scheme のように、変数の値を書き換えることができる処理系では、クロージャに保存された変数の値を変更することが可能です。興味のある方は拙作のページお気楽 Common Lisp プログラミング入門レキシカルスコープとクロージャをお読みください。

●関数適用演算子 $

Haskell には関数を適用する演算子 $ が用意されています。関数を f, 引数を x とすると、f $ x は f x と同じ働きをします。実際に型を調べると次のように表示されます。

Prelude> :t ($)
($) :: (a -> b) -> a -> b

カリー化関数の場合、優先順位が高くて左結合なので、f a b c は (((f a) b) c) と解釈されます。これに対して、演算子 $ の優先順位は低くて右結合なので、f $ a $ b c は f (a (b c)) と解釈されます。つまり、カッコの数を減らすことができるわけです。

たとえば、関数 sum_of の定義は次のように書き直すことができます。

sum_of f n m = sum (map f [n .. m]) => sum $ map f [n .. m]

もうひとつ例を示しましょう。リストの要素から 5 を引いて、結果がプラスとなる要素の総和を求めるプログラムは、sum, filter, map を組み合わせて次のように書くことができます。

Prelude> sum (filter (>0) (map ((-)5) [5,6,4,7,3,8,2,9,1]))
10
Prelude> sum $ filter (>0) (map ((-)5) [5,6,4,7,3,8,2,9,1])
10

このように、$ を使うとカッコの数を減らすことができます。

また、リストに格納された関数に引数を渡して評価するときにも演算子 $ を使うことができます。簡単な例を示しましょう。

Prelude> map ($ 10) [(+10), (*10), (2^)]
[20,100,1024]

このように、リストの中の関数に引数 10 が渡されて評価されるので、10+10=20, 10*10=100, 2^10=1024 という結果になります。

●関数の合成

最後に、関数 f(x) と g(x) を合成して新しい関数 h(x) を作ることを考えてみましょう。関数 h(x) を次のように定義します。

h(x) = f( g( x ) )

たとえば、f(x) = 2 * x + 1, g(x) = x * x + 3 * x とすると、h(x) は次のようになります。

h(x) = f( g( x ) )
     = 2 * (x * x + 3 * x) + 1
     = 2 * x * x + 6 * x + 1

実際のプログラムは数式を展開するのではなく、g(x) の評価結果を f(x) に渡すだけなので簡単です。第 1 引数と第 2 引数に関数 f と g を受け取り、それらを第 3 引数に適用する関数 compose は次のようになります。

Prelude> compose f g x = f (g x)
Prelude> :t compose
compose :: (t1 -> t2) -> (t3 -> t1) -> t3 -> t2

関数 g(x) の返り値が関数 f(x) の引数になるので、関数 f(x) が受け付ける値でなければいけません。そうでないと関数を合成することはできません。この条件を関数 compose の型が表しています。関数 g の返り値が型 t1 ならば、関数 f の引数も型は t1 でなければいけません。

簡単な例を示しましょう。

Prelude> f x = 2 * x + 1
Prelude> g x = x * x + 3 * x
Prelude> f (g 4)
57
Prelude> h = compose f g
Prelude> h 4
57

関数 f と g を定義します。f と g の合成は f( g( x ) ) と表すことができます。実際に 4 を計算すると 57 になります。この関数は compose で合成することができます。compose f g の返り値を変数 h に束縛すると、h を合成関数として使うことができます。

Haskell には compose と同じ働きをする演算子 . が用意されています。

Prelude> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

演算子 . は右結合なので、f (g (h x)) は (f . g . h) x と同じです。簡単な例を示しましょう。

Prelude> (f . g) 4
57
Prelude> f . g $ 4
57
Prelude> sum $ filter (>0) $ map ((-)5) [5,6,4,7,3,8,2,9,1]
10
Prelude> sum . filter (>0) . map ((-)5) $ [5,6,4,7,3,8,2,9,1]
10

f . g 4 とすると、カリー化関数の優先順位が高いため、g 4 を評価してから f と関数合成しようとするためエラーになります。(f . g) 4 のように括弧をつけたくない場合は $ を使って f . g $ 4 とします。$ の優先順位が低いので、f . g で合成された関数に引数 4 が渡されます。

関数合成は 1 引数の関数でなければいけません。最後の例で、filter (>0) と map (\x -> x - 5) は部分適用により 1 引数の関数として扱うことができます。したがって、sum といっしょに関数合成して、それをリストに適用することができます。

この処理を関数 foo として定義する場合、関数合成を使ってポイントフリースタイルで記述することができます。

Prelude> foo = sum . filter (>0) . map ((-)5)
Prelude> :t foo
foo :: (Num c, Ord c) => [c] -> c
Prelude> foo [5,6,4,7,3,8,2,9,1]
10

このように、小さな関数を合成して大きな関数を組み立てることは、Haskell でよく行われる方法です。

●問題

次の関数を定義してください。

要素 x を n 個格納したリストを生成する make_list n x

Haskell には make_list と同じ働きをする関数 replicate がある

マッピングした結果を平坦化する関数 flatmap fn xs

Haskell のモジュール Data.List には同様の関数 concat と concatMap がある

述語 pred を満たす要素が続いている間、リスト xs の先頭から順番に要素を取り出す関数 takeWhile' pred xs
述語 pred を満たす要素が続いている間、リスト xs の先頭から順番に要素を取り除く関数 dropWhile' pred xs

Haskell のモジュール Data.List には同様の関数 takeWhile と dropWhile がある

リスト xs の中で連続した等しい要素を部分リストにまとめる関数 pack xs
リストの中で連続している同じ記号を (code, num) に変換する関数 encode xs
encode xs の逆変換を行う関数 decode xs

●解答

リスト : 解答例 (q06.hs)

make_list :: Int -> a -> [a]
make_list 0 _ = []
make_list n x = x : make_list (n - 1) x

flatmap :: (a -> [b]) -> [a] -> [b]
flatmap _ [] = []
flatmap fn (x:xs) = fn x ++ flatmap fn xs

takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' _ [] = []
takeWhile' pred (x:xs) =
  if pred x then x : takeWhile' pred xs else []

dropWhile' :: (a -> Bool) -> [a] -> [a]
dropWhile' _ [] = []
dropWhile' pred ys@(x:xs) =
  if pred x then dropWhile' pred xs else ys

pack :: Eq a => [a] -> [[a]]
pack [] = []
pack ys@(x:_) =
  takeWhile' (==x) ys : pack (dropWhile' (==x) ys)

encode :: Eq a => [a] -> [(a, Int)]
encode xs = map (\ys -> (head ys, length ys)) $ pack xs

decode :: [(a, Int)] -> [a]
decode xs = flatmap (\(x, n) -> make_list n x) xs

Prelude> :l q06.hs
[1 of 1] Compiling Main             ( q06.hs, interpreted )
Ok, one module loaded.
*Main> make_list 10 1
[1,1,1,1,1,1,1,1,1,1]
*Main> make_list 10 1.25
[1.25,1.25,1.25,1.25,1.25,1.25,1.25,1.25,1.25,1.25]
*Main> make_list 10 'a'
"aaaaaaaaaa"
*Main> make_list 10 "foo"
["foo","foo","foo","foo","foo","foo","foo","foo","foo","foo"]

*Main> flatten [[1,2,3],[4,5],[6,7,8,9]]
[1,2,3,4,5,6,7,8,9]
*Main> flatten [[1,2,3],[4,5],[],[6,7,8,9]]
[1,2,3,4,5,6,7,8,9]
*Main> flatten [[[1,2,3]],[[4,5,6,7]]]
[[1,2,3],[4,5,6,7]]

*Main> map (\x -> [x, x]) [1,2,3,4,5]
[[1,1],[2,2],[3,3],[4,4],[5,5]]
*Main> flatmap (\x -> [x, x]) [1,2,3,4,5]
[1,1,2,2,3,3,4,4,5,5]
*Main> flatmap (\x -> make_list x x) [1,2,3,4,5]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]

*Main> takeWhile' (<5) [1 .. 10]
[1,2,3,4]
*Main> takeWhile' (<11) [1 .. 10]
[1,2,3,4,5,6,7,8,9,10]
*Main> takeWhile' (<0) [1 .. 10]
[]

*Main> dropWhile' (<5) [1 .. 10]
[5,6,7,8,9,10]
*Main> dropWhile' (<11) [1 .. 10]
[]
*Main> dropWhile' (<0) [1 .. 10]
[1,2,3,4,5,6,7,8,9,10]

*Main> pack [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]
[[1],[2,2],[3,3,3],[4,4,4,4],[5,5,5,5,5]]
*Main> pack [1,2,3,4,5,6,7,8,9,10]
[[1],[2],[3],[4],[5],[6],[7],[8],[9],[10]]
*Main> pack [1,1,1,1,1,1,1,1,1,1]
[[1,1,1,1,1,1,1,1,1,1]]

*Main> encode [1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]
[(1,1),(2,2),(3,3),(4,4),(5,5)]
*Main> encode [1,2,3,4,5,6,7,8,9,10]
[(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(9,1),(10,1)]
*Main> encode [1,1,1,1,1,1,1,1,1,1]
[(1,10)]

*Main> decode [(1,1),(2,2),(3,3),(4,4),(5,5)]
[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5]
*Main> decode [(1, 10)]
[1,1,1,1,1,1,1,1,1,1]
*Main> decode [(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(9,1),(10,1)]
[1,2,3,4,5,6,7,8,9,10]

encode のような変換を「ランレングス符号化」という

初版 2013 年 1 月 20 日
改訂 2021 年 1 月 10 日

Functional Programming