Lisp. ML, Haskell などの関数型言語は、関数を他のデータ型と同等に取り扱うことができます。つまり、関数を変数に代入したり、引数として渡すことができます。また、値として関数を返すこともできるので、関数を作る関数を定義することもできます。関数を引数にとる関数のことを「汎関数 (functional)」とか「高階関数 (higher order function)」と呼びます。
Haskell は高階関数を簡単に定義することができます。もちろん、値として関数を返すこともできるので、関数を作る関数を定義することも簡単です。実際、関数の操作は Common Lisp よりも柔軟で簡単です。
簡単な例として、整数 n から m までの和を求める関数 sum_of_integer を作ってみましょう。プログラムは次のようになります。
リスト : 整数の和 sum_of_integer :: (Integer, Integer) -> Integer sum_of_integer (n, m) | n > m = 0 | otherwise = n + sum_of_integer (n + 1, m)
実行例を示します。
ghci> sum_of_integer (1, 10) 55 ghci> sum_of_integer (1, 100) 5050
プログラムは簡単なので説明は不要でしょう。それでは、整数の 2 乗の和と 3 乗の和を求めるプログラムはどうなるでしょうか。次のリストを見てください。
リスト : 整数の 2 乗の和と 3 乗の和 -- 2 乗 square :: Num a => a -> a square x = x * x -- 3 乗 cube :: Num a => a -> a cube x = x * x * x -- 2 乗の和 sum_of_square :: (Integer, Integer) -> Integer sum_of_square (n, m) | n > m = 0 | otherwise = square n + sum_of_square (n + 1, m) -- 3 乗の和 sum_of_cube :: (Integer, Integer) -> Integer sum_of_cube (n, m) | n > m = 0 | otherwise = cube n + sum_of_cube (n + 1, m)
実行例を示します。
ghci> sum_of_square (1, 10) 385 ghci> sum_of_square (1, 100) 338350 ghci> sum_of_cube (1, 10) 3025 ghci> sum_of_cube (1, 100) 25502500
n を加算する処理で、関数 square を呼び出すと 2 乗の和、関数 cube を呼び出すと 3 乗の和を求めることができます。関数 sum_of_square と sum_of_cube の違いはこれだけです。ここで、square や cube を引数として渡すことができれば、sum_of_square や sum_of_cube を一つの関数で済ますことができます。次のリストを見てください。
リスト : 高階関数 sum_of sum_of :: (Integer -> Integer, Integer, Integer) -> Integer sum_of (f, n, m) | n > m = 0 | otherwise = f n + sum_of (f, n + 1, m)
関数 sum_of の引数 f に関数を渡します。渡された関数は、今までと同じ方法で呼び出すことができます。square や cube のかわりに f n + sum_of ... とすることで、関数 f に整数 n を適用した結果を sum_of の返り値に加算することができます。
簡単な実行例を示します。
ghci> sum_of (square, 1, 10) 385 ghci> sum_of (cube, 1, 10) 3025
高階関数を使うようになると、数を 2 乗する square のような小さな関数をいちいち定義するのが面倒になります。とくに、その高階関数でしか使わないのであれば、なおさらそう思うでしょう。Haskell には Lisp と同様の「ラムダ式」という名前のない関数が用意されています。
Haskell の場合、ラムダ式は次のように定義します。
\ 引数 -> 式
関数定義はラムダ式を用いて次のように表すことができます。
func = \ 引数 -> 式
ラムダ式は関数型のデータを生成して返します。そして、関数定義は変数 func をその値に束縛するだけなのです。また、Haskell はラムダ式をそのまま実行することができますし、関数の引数にラムダ式を渡すこともできます。
簡単な例を示します。
ghci> (\x -> x * x) 5 25 ghci> (\(x,y) -> x + y) (1, 2) 3 ghci> sum_of (\x -> x * x, 1, 10) 385
ところで、今まではタプルを使って複数の引数を受け取る関数を実現しましたが、Haskell にはもう一つ方法があります。関数型言語は関数をデータ型の一つとして扱うことができるので、関数の返り値として関数を返すことができます。この「関数を返す関数」を使うと、関数の引数が一つでも複数の引数を処理することができます。このような関数を「カリー化関数 (curried function)」といいます。
たとえば、\(x, y) -> x + y の場合、引数 x を受け取ると「引数 y を受け取って x + y を計算する関数」を返し、その関数に引数 y を渡せば x + y を計算することができます。Haskell では、次のように定義することができます。
ghci> :t \x -> \y -> x + y \x -> \y -> x + y :: Num a => a -> a -> a
関数の型が少し複雑になりました。-> は右結合なので、a -> a -> a は a -> (a -> a) となります。これは引数 a を受け取り、a -> a という型の関数を返すことを表しています。これで引数を一つだけ与えれば、関数を返すことになります。もちろん、引数を 2 つ与えれば、それらを加算した結果を返します。つまり、最初の引数を受け取って関数を生成し、その関数を 2 番目の引数に適用する、という動作になります。
それでは実際に試してみましょう。
ghci> :t (\x -> \y -> x + y) 1 (\x -> \y -> x + y) 1 :: Num a => a -> a ghci> (\x -> \y -> x + y) 1 2 3
引数を一つだけ渡すと「引数 y を受け取って x + y を計算する関数」を返します。引数を 2 つ渡すと、それを足し算した値を返します。カリー化関数の場合、引数は空白で区切ることに注意してください。
ラムダ式を入れ子にするのは面倒なので、Haskell は次のようにカリー化関数を定義することができます。
\ 引数1 引数2 ... 引数n -> 式
また、関数定義でも同様にカリー化関数を定義することができます。
名前 引数1 引数2 ... 引数n = 式
関数をカリー化する場合、引数をカッコで囲わず、カンマでも区切りません。たとえば、関数 sum_of をカリー化すると次のようになります。
リスト : 関数 sum_of のカリー化 sum_of' :: (Integer -> Integer) -> Integer -> Integer -> Integer sum_of' f n m | n > m = 0 | otherwise = f n + sum_of' f (n + 1) m
そして、この sum_of' を使うと、sum_of_integer, sum_of_square, sum_of_cube を簡単に定義することができます。
ghci> sum_of_integer' = sum_of' id ghci> sum_of_square' = sum_of' square ghci> sum_of_cube' = sum_of' cube ghci> :t sum_of_integer' sum_of_integer' :: Integer -> Integer -> Integer ghci> :t sum_of_square' sum_of_square' :: Integer -> Integer -> Integer ghci> :t sum_of_cube' sum_of_cube' :: Integer -> Integer -> Integer ghci> sum_of_integer' 1 10 55 ghci> sum_of_square' 1 10 385 ghci> sum_of_cube' 1 10 3025
sum_of_integer', sum_of_square', sum_of_cube' は引数 s, e を省略して定義していますね。このような関数定義を「ポイントフリースタイル」といいます。関数 g の定義が g x = f x とすると、引数 x のことを「ポイント」と呼びます。この場合、引数 x を省略して関数定義を g = f と表すことができます。
sum_of_cube' の場合、引数を記述すると次のようになります。
sum_of_cube' s e = sum_of' cube s e => sum_of_cube' s = sum_of' cube s => sum_of_cube' = sum_of' cube
右辺と左辺で最後の引数は同じ e なので、省略することが可能です。e を省略したあと、右辺左辺ともに最後の引数は s になりますね。これも省略することができます。したがって、関数定義は sum_of_cube' = sum_of' cube となります。
このように、カリー化された関数の一部の引数に値を与えて、残りの引数を受け取る関数を生成することを「部分適用 (partial application)」といいます。カリー化関数は部分適用が簡単にできるのでとても便利です。Haskell の場合、カリー化関数はよく使われる方法です。
Haskell は数列を表すリストを簡単に生成することができます。この機能を「レンジ (range)」といいます。構文は次のようになります。
(1) [s .. e] => [s, s+1, s+2, ..., e-1, e] (2) [s, s+a, .. e] => [s, s+a, s+a*2, s+a*3, ..., e]
(1) のように開始 s と終了 e の値 (s < e) を指定すると、s 以上 e 以下の数列が生成されます。s > e の場合は空リストになります。簡単な例を示しましょう。
ghci> [1 .. 10] [1,2,3,4,5,6,7,8,9,10] ghci> [10 .. 1] []
(2) は初項と第 2 項で差分を指定します。つまり、公差 a の等差数列になります。差分が負の場合、s < e は空リストになります。簡単な例を示しましょう。
ghci> [1,3 .. 10] [1,3,5,7,9] ghci> [1,4 .. 10] [1,4,7,10] ghci> [10, 9 .. 1] [10,9,8,7,6,5,4,3,2,1] ghci> [10, 9 .. 11] []
レンジは整数だけではなく型クラス Enum のインスタンスであれば使用することができます。簡単な例を示します。
ghci> ['a' .. 'z'] "abcdefghijklmnopqrstuvwxyz" ghci> ['a', 'c' .. 'z'] "acegikmoqsuwy" ghci> [1.0 .. 10.0] [1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0] ghci> [1.0, 1.25 .. 2.0] [1.0,1.25,1.5,1.75,2.0]
このように、Haskell ではレンジを使ってリストを簡単に生成することができます。
Haskell は中置演算子をカッコで囲むとカリー化関数として扱うことができます。簡単な例を示しましょう。
ghci> (+) 1 2 3 ghci> (*) 1 2 2 ghci> (^) 2 3 8
中置演算子の場合、部分適用には特別な構文が用意されています。次の例を見てください。
ghci> (+1) 2 3 ghci> (*10) 2 20 ghci> (^2) 3 9 ghci> (2^) 3 8
演算子を op, 引数を x, y とすると、 (op y) x は x op y を意味し、(y op) x は y op x を意味します。この機能を「セクション」と呼びます。高階関数を使う場合、セクションはとても役に立ちます。たとえば、sum_of_square, sum_of_cube は次のように定義できます。
リスト : sum_of_square, sum_of_cube の定義 sum_of_square = sum_of' (^2) sum_of_cube = sum_of' (^3)
なお、演算子 - を部分適用することはできません。(-2) は -2 という負の数として解釈されます。ご注意くださいませ。
次の関数をカリー化関数を使って定義してください。
リスト : 問題の解答例 (q04.hs) append :: [a] -> [a] -> [a] append [] ys = ys append (x:xs) ys = x : append xs ys longer :: [a] -> [a] -> Bool longer [] _ = False longer _ [] = True longer (_:xs) (_:ys) = longer xs ys take' :: Int -> [a] -> [a] take' 0 _ = [] take' _ [] = [] take' n (x:xs) = x : take' (n - 1) xs drop' :: Int -> [a] -> [a] drop' 0 xs = xs drop' _ [] = [] drop' n (_:xs) = drop (n - 1) xs nth :: Int -> [a] -> a nth _ [] = error "nth: empty list" nth 0 (x:_) = x nth n (_:xs) = nth (n - 1) xs member :: Eq a => a -> [a] -> [a] member _ [] = [] member x xs@(y:ys) | x == y = xs | otherwise = member x ys member_if :: (a -> Bool) -> [a] -> [a] member_if _ [] = [] member_if pred ys@(x:xs) | pred x = ys | otherwise = member_if pred xs partition_if :: (a -> Bool) -> [a] -> ([a],[a]) partition_if _ [] = ([], []) partition_if pred (x:xs) = if pred x then (x:a, b) else (a, x:b) where (a, b) = partition_if pred xs iota :: Integral a => a -> a -> [a] iota s e | s > e = [] | otherwise = s : iota (s + 1) e tabulate :: Integral a => (a -> b) -> a -> a -> [b] tabulate f s e | s > e = [] | otherwise = f s : tabulate f (s + 1) e
ghci> :l q04.hs [1 of 1] Compiling Main ( q04.hs, interpreted ) Ok, one module loaded. ghci> append [1,2,3] [4,5,6] [1,2,3,4,5,6] ghci> append [1,2,3] [] [1,2,3] ghci> append [] [4,5,6] [4,5,6] ghci> longer [1,2,3] [4,5,6] False ghci> longer [1,2,3] [4,5] True ghci> longer [1,2,3] [4,5,6,7] False ghci> take' 3 [1,2,3,4,5] [1,2,3] ghci> take' 0 [1,2,3,4,5] [] ghci> take' 5 [1,2,3,4,5] [1,2,3,4,5] ghci> drop' 3 [1,2,3,4,5] [4,5] ghci> drop' 0 [1,2,3,4,5] [1,2,3,4,5] ghci> drop' 5 [1,2,3,4,5] [] ghci>> nth 0 [1,2,3,4,5] 1 ghci>> nth 2 [1,2,3,4,5] 3 ghci>> nth 4 [1,2,3,4,5] 5 ghci>> nth 5 [1,2,3,4,5] *** Exception: nth: empty list ghci>> member 1 [1,2,3,4,5] [1,2,3,4,5] ghci>> member 5 [1,2,3,4,5] [5] ghci>> member 6 [1,2,3,4,5] [] ghci>> member_if (\x -> x > 3) [1,2,3,4,5] [4,5] ghci>> member_if (\x -> x < 2) [1,2,3,4,5] [1,2,3,4,5] ghci>> member_if (\x -> x < 0) [1,2,3,4,5] [] ghci>> partition_if even [1,2,3,4,5,6,7,8] ([2,4,6,8],[1,3,5,7]) ghci>> partition_if odd [1,2,3,4,5,6,7,8] ([1,3,5,7],[2,4,6,8]) ghci>> partition_if (\x -> x > 4) [1,2,3,4,5,6,7,8] ([5,6,7,8],[1,2,3,4]) ghci>> iota 1 10 [1,2,3,4,5,6,7,8,9,10] ghci>> iota 10 10 [10] ghci>> iota 11 10 [] ghci>> tabulate (*10) 1 10 [10,20,30,40,50,60,70,80,90,100] ghci>> tabulate (^2) 1 10 [1,4,9,16,25,36,49,64,81,100]