変数の有効範囲を表す用語に「スコープ (scope)」があります。この用語を使うと、厳密ではありませんが、変数の有効範囲は「レキシカルスコープ (lexical scope)」と「ダイナミックスコープ (dynamic scope)」の 2 つに分けることができます。
伝統的な Lisp はダイナミックスコープですが、現在のプログラミング言語、たとえば、Scheme, Common Lisp, SML/NJ, OCaml, Haskell はレキシカルスコープを採用しています。
それでは、レキシカルスコープについて詳しく見てみましょう。引数を無視して変数 x の値を返す関数 foo を定義します。
ghci> x = 10 ghci> foo a = x ghci> foo 0 10
関数 foo には局所変数 x を定義していないので、foo を実行した場合は大域変数の値を参照します。その結果、返り値は 10 となります。それでは、foo1 という関数から foo を呼び出す場合を考えてみましょう。foo1 には let で局所変数 x を定義します。この場合、foo はどちらの値を返すのでしょうか。実際に試してみましょう。
ghci> foo1 b = let x = 100 in foo b ghci> foo1 0 10
foo1 を実行すると大域変数の値 10 を返しました。このように、foo1 で定義した局所変数 x は、foo から参照することはできません。次の図を見てください。
┌────── Haskell system ──────┐
│ │
│ 大域変数 x ←────┐ │
│ │ │
│ ┌→┌─ 関数 foo ──────┐ │ │
│ │ │ ┌──────┼─┘ │
│ │ │ x │ │
│ │ │ │ │
│ │ └────────────┘ │
│ │ ┌─ 関数 foo1 ─────┐ │
│ │ │ │ │
│ │ │ ┌─let : x ───┐ │ │
│ │ │ │ │ │ │
│ └─┼─┼─ foo 0 │ │ │
│ │ └────────┘ │ │
│ └────────────┘ │
│ │
└────────────────────┘
図 : レキシカルスコープ
上図では変数の有効範囲を枠で表しています。foo1 の let で定義した局所変数 x は、let の枠の中でのみ有効です。もしも、この枠で変数が見つからない場合は、ひとつ外側の枠を調べます。
順番に外側の枠を調べていくと、最後には関数定義の枠に行き着きます。ここで変数 (引数) が見つからない場合は大域変数を調べます。
関数 foo は関数定義の枠しかありません。そこに変数 x が定義されていないので、大域変数を調べることになるのです。このように、関数 foo から foo1 の枠と let の枠を超えて変数 x にアクセスすることはできないのです。
これを「レキシカルスコープ」といいます。レキシカルには文脈上いう意味があり、変数が定義されている構造の範囲内 (枠内) でないと、その変数にアクセスすることはできません。
ところが伝統的な Lisp の場合、foo1 で定義した変数 x は呼び出された関数 foo からアクセスすることができます。これを「ダイナミックスコープ」といいます。
foo1 で定義された変数 x は、foo1 の実行が終了するまで存在します。そして、foo1 から呼ばれた関数ならば、どこからでも参照することができるのです。もしも、foo1 をダイナミックスコープの処理系、たとえば Emacs Lisp で実行するならば、foo が返す x の値は 100 になります。
それでは、関数の中で定義された局所関数やラムダ式の場合はどうなるのでしょうか。次の例を見てください。
ghci> times_element n xs = map (\x -> x * n) xs ghci> times_element 10 [1,2,3,4,5,6] [10,20,30,40,50,60]
ラムダ式の引数は x だけなので、変数 n は大域変数を参照するように思われるかもしれません。ところが、変数 n は関数 times_element の引数 n を参照するのです。これを図に示すと、次のようになります。
┌───── Haskell system ──────┐
│ │
│ ┌─ times_element : n xs ─┐ │
│ │ ↑ │ │
│ │ └─┐ │ │
│ │ ┌──lambda: x ─┐│ │ │
│ │ │ ↑ ││ │ │
│ │ │ ┌───┘ ││ │ │
│ │ │ x * n ││ │ │
│ │ │ └───┼┘ │ │
│ │ └────────┘ │ │
│ └─────────────┘ │
│ │
└───────────────────┘
図 : 匿名関数内の変数
ポイントは、ラムダ式が times_element 内で定義されているところです。変数 n は関数の引数として定義されていて、その有効範囲は関数の終わりまでです。ラムダ式はその範囲内に定義されているため、変数 n にアクセスすることができるのです。つまり、関数内で定義されたラムダ式は、そのとき有効な局所変数にアクセスすることができるのです。
これは let で定義された局所的な関数も同じです。times_element は次のように書き換えることができます。
ghci> times_element n xs = let timesN x = x * n in map timesN xs ghci> times_element 10 [1,2,3,4,5,6] [10,20,30,40,50,60]
局所関数 timesN は times_element 内で定義されているので、timesN から times_element の引数 n を参照することができます。
もちろん、セクションを使っても動作します。
ghci> times_element n xs = map (*n) xs ghci> times_element 10 [1,2,3,4,5,6] [10,20,30,40,50,60]
Haskell の場合、これが一番簡単ですね。
Lisp などの関数型言語では、関数を生成する関数を簡単に作ることができます。このとき使われる機能が「クロージャ (closure)」です。
クロージャは評価する関数と参照可能な局所変数をまとめたものです。クロージャは関数のように実行することができますが、クロージャを生成するときに参照可能な局所変数を保持するところが異なります。参照可能な局所変数の集合を「環境」と呼ぶことがあります。
Haskell の関数はカリー化できるので、関数を返す関数はとても簡単に作成することができます。また、Haskell は関数型言語なので、当然ですがクロージャも使うことができます。
Haskell でクロージャを生成するにはラムダ式を使うか、局所的な関数を定義して、その関数を返します。たとえば、「引数を n 倍する関数」を生成する関数は、ラムダ式を使うと次のようになります。
ghci> foo n = \x -> x * n ghci> :t foo foo :: Num a => a -> a -> a ghci> foo10 = foo 10 ghci> :t foo10 foo10 :: Num a => a -> a ghci> foo10 10 100 ghci> foo10 20 200 ghci> foo10 1.25 12.5 ghci> foo100 = foo 100 ghci> foo100 10 1000 ghci> foo100 20 2000 ghci> foo100 1.25 125.0 ghci> foo5 = foo 5 ghci> foo5 10 50 ghci> foo5 20 100 ghci> 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 を使った例を示します。
ghci> foo n = let bar x = x * n in bar ghci> foo100 = foo 100 ghci> foo100 10 1000 ghci> foo5 = foo 5 ghci> foo5 10 50
関数 bar を定義して、bar を返します。すると、foo は「引数を n 倍する関数」を生成する関数になります。
もっとも、Haskell では関数をカリー化するだけで同様の関数を作ることができます。
ghci> foo n x = n * x ghci> :t foo foo :: Num a => a -> a -> a ghci> foo100 = foo 100 ghci> :t foo100 foo100 :: Num a => a -> a ghci> foo100 10 1000 ghci> foo5 = foo 5 ghci> foo5 10 50
このように、Haskell は関数をカリー化できるので、部分適用により目的の関数を簡単に生成することができます。
クロージャを理解する場合、環境を「連想リスト (association list : a-list)」で考えるとわかりやすいと思います。ここで簡単に連想リストについて説明します。
連想リストは Lisp でよく用いられるデータ構造で、Haskell ではキーとデータのタプルを要素とするリストで実現することができます。データ型で記述すると [(a, b)] になり、a がキーで b がデータに対応します。
┌────┬────┬────┬──→ データ
│ │ │ │
連想リスト => [("a", 1), ("b", 2), ("c", 3), ("d", 4)]
│ │ │ │
└────┴────┴────┴──→ キー
図 : 連想リストの構造
上図の場合、文字列 "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 と同じ働きをします。実際に型を調べると次のように表示されます。
ghci> :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 を組み合わせて次のように書くことができます。
ghci> sum (filter (>0) (map ((-)5) [5,6,4,7,3,8,2,9,1])) 10 ghci> sum $ filter (>0) (map ((-)5) [5,6,4,7,3,8,2,9,1]) 10
このように、$ を使うとカッコの数を減らすことができます。
また、リストに格納された関数に引数を渡して評価するときにも演算子 $ を使うことができます。簡単な例を示しましょう。
ghci> 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 は次のようになります。
ghci> compose f g x = f (g x) ghci> :t compose compose :: (t1 -> t2) -> (t3 -> t1) -> t3 -> t2
関数 g(x) の返り値が関数 f(x) の引数になるので、関数 f(x) が受け付ける値でなければいけません。そうでないと関数を合成することはできません。この条件を関数 compose の型が表しています。関数 g の返り値が型 t1 ならば、関数 f の引数も型は t1 でなければいけません。
簡単な例を示しましょう。
ghci> f x = 2 * x + 1 ghci> g x = x * x + 3 * x ghci> f (g 4) 57 ghci> h = compose f g ghci> h 4 57
関数 f と g を定義します。f と g の合成は f( g( x ) ) と表すことができます。実際に 4 を計算すると 57 になります。この関数は compose で合成することができます。compose f g の返り値を変数 h に束縛すると、h を合成関数として使うことができます。
Haskell には compose と同じ働きをする演算子 . が用意されています。
ghci> :t (.) (.) :: (b -> c) -> (a -> b) -> a -> c
演算子 . は右結合なので、f (g (h x)) は (f . g . h) x と同じです。簡単な例を示しましょう。
ghci> (f . g) 4 57 ghci> f . g $ 4 57 ghci> sum $ filter (>0) $ map ((-)5) [5,6,4,7,3,8,2,9,1] 10 ghci> 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 として定義する場合、関数合成を使ってポイントフリースタイルで記述することができます。
ghci> foo = sum . filter (>0) . map ((-)5) ghci> :t foo foo :: (Num c, Ord c) => [c] -> c ghci> foo [5,6,4,7,3,8,2,9,1] 10
このように、小さな関数を合成して大きな関数を組み立てることは、Haskell でよく行われる方法です。
次の関数を定義してください。
リスト : 解答例 (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
ghci> :l q06.hs [1 of 1] Compiling Main ( q06.hs, interpreted ) Ok, one module loaded. ghci> make_list 10 1 [1,1,1,1,1,1,1,1,1,1] ghci> 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] ghci> make_list 10 'a' "aaaaaaaaaa" ghci> make_list 10 "foo" ["foo","foo","foo","foo","foo","foo","foo","foo","foo","foo"] ghci> flatten [[1,2,3],[4,5],[6,7,8,9]] [1,2,3,4,5,6,7,8,9] ghci> flatten [[1,2,3],[4,5],[],[6,7,8,9]] [1,2,3,4,5,6,7,8,9] ghci> flatten [[[1,2,3]],[[4,5,6,7]]] [[1,2,3],[4,5,6,7]] ghci> map (\x -> [x, x]) [1,2,3,4,5] [[1,1],[2,2],[3,3],[4,4],[5,5]] ghci> flatmap (\x -> [x, x]) [1,2,3,4,5] [1,1,2,2,3,3,4,4,5,5] ghci> 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] ghci> takeWhile' (<5) [1 .. 10] [1,2,3,4] ghci> takeWhile' (<11) [1 .. 10] [1,2,3,4,5,6,7,8,9,10] ghci> takeWhile' (<0) [1 .. 10] [] ghci> dropWhile' (<5) [1 .. 10] [5,6,7,8,9,10] ghci> dropWhile' (<11) [1 .. 10] [] ghci> dropWhile' (<0) [1 .. 10] [1,2,3,4,5,6,7,8,9,10] ghci> 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]] ghci> pack [1,2,3,4,5,6,7,8,9,10] [[1],[2],[3],[4],[5],[6],[7],[8],[9],[10]] ghci> pack [1,1,1,1,1,1,1,1,1,1] [[1,1,1,1,1,1,1,1,1,1]] ghci> 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)] ghci> 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)] ghci> encode [1,1,1,1,1,1,1,1,1,1] [(1,10)] ghci> 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] ghci> decode [(1, 10)] [1,1,1,1,1,1,1,1,1,1] ghci> 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]