プログラムを作っていると、以前作った関数と同じ処理が必要になる場合があります。いちばんてっとり早い方法はソースファイルからその関数をコピーすることですが、賢明な方法とはいえません。このような場合、自分で作成した関数をライブラリとしてまとめておくと便利です。
ライブラリの作成で問題になるのが「名前の衝突」です。複数のライブラリを使うときに、同じ名前の関数や変数が存在すると、そのライブラリは正常に動作しないでしょう。この問題は「モジュール (module)」を使うと解決することができます。
モジュールを簡単に説明すると、データ構造とそれを操作する関数を一つにまとめるための仕組みです。最近は、モジュールに相当する機能を持つプログラミング言語が多くなりました。Haskell にもモジュールがあるので、データ構造や関数をモジュールにまとめておけば、ユーザーにとって使いやすいライブラリを構築することができます。
実際、Haskell には多くのモジュールが標準で添付されています。これらのモジュールを使うことで、プログラムを効率的に開発することができます。
Haskell の場合、モジュールは import 文を使って読み込みます。
import モジュール名
import 文で指定できるモジュールは一つだけです。複数のモジュールを読み込む場合は、モジュールの数だけ import 文を記述してください。
ghci の場合、コマンド :m でモジュールを読み込むことができます。
:m + モジュール名 ...
:m コマンドは複数のモジュールを指定することができます。その場合はモジュール名を空白で区切ってください。
簡単な例を示します。
ghci> :t union <interactive>:1:1: error: [GHC-88464] Variable not in scope: union ghci> :m + Data.List ghci> :t union union :: Eq a => [a] -> [a] -> [a] ghci> union [1,2,3,4] [3,4,5,6] [1,2,3,4,5,6]
union は集合 (リスト) の和を求める関数で、モジュール Data.List に定義されています。Data.List をロードすると union を利用することができます。
必要な関数 (変数) だけインポートすることもできます。
import モジュール名 (名前, ...)
モジュール名の後ろのカッコの中にインポートする関数を指定します。逆に、インポートしたくない関数を指定することもできます。
import モジュール名 hiding (名前, ...)
hiding を付けると、指定された関数はインポートされません。それ以外の関数はすべてインポートされます。
複数のモジュールをインポートすると、名前が重複する場合があります。名前の重複を避けるため、Haskell には別名を付ける方法が用意されています。
import qualified モジュール名
qualified を指定すると、"モジュール名" + "." + "名前" でアクセスすることができます。これを「修飾付きインポート」といいます。このとき、モジュール名が長いとプログラムを書くのが面倒になるので、次のように別名を指定することができます。
import qualified モジュール名 as 別名
as の後ろに名前 (別名) を指定します。これで "別名" + "." + "名前" でアクセスすることができます。
モジュールは module を使って定義します。
module モジュール名 (名前, ...) where
通常はファイルの先頭に module を記述します。たとえば、モジュール名を Foo とすると、ファイル名はモジュール名と同じ名前 Foo.hs としなければなりません。モジュール名の後のカッコの中にはエクスポート (export) する名前 (関数名、変数名、型構築子、データ構築子など) を記述します。省略した場合はモジュールで定義されたすべての名前がエクスポートされます。そして、where 以降にモジュールに格納するデータ構造や関数を定義します。where はレイアウトが使えますが、モジュールの場合はインデントしないで行頭からプログラムを書くのが一般的なようです。
import でインポートされる名前は、module でエクスポートされている名前だけです。エクスポートされていない名前はインポートすることができません。モジュール内だけで使用する関数は、エクスポートしなければ「非公開」となります。同様に、データ構築子をエクスポートしないと、データを生成したりパターンマッチングでデータを取り出すことができなくなります。この場合、公開されている関数だけを使ってデータ構造にアクセスすることになります。
簡単な例を示しましょう。
リスト : Fruit.hs module Fruit (Fruit(..), getPrice) where data Fruit = Apple | Grape | Orange deriving (Show, Eq) priceList :: [(Fruit, Integer)] priceList = [(Apple, 100), (Grape, 150), (Orange, 200)] getPrice :: Fruit -> Maybe Integer getPrice x = lookup x priceList リスト : fruit1.hs import Fruit sumPrice :: [Fruit] -> Integer sumPrice xs = foldl (\a x -> let (Just v) = getPrice x in a + v) 0 xs
モジュール Fruit にはデータ型 Fruit の定義と果物の値段が記述されています。型構築子とデータ構築子は次のようにエクスポートします。
1. 型構築子(データ構築子, ...) 2. 型構築子(..)
型構築子の後ろのカッコの中にデータ構築子を指定します。データ構築子が複数ある場合はカンマで区切ります。2 番目のようにカッコの中で記号 .. を指定すると、型構築子で定義されているデータ構築子がすべてエクスポートされます。priceList は果物の値段を表す連想リストです。getPrice は priceList から果物の値段を求める関数です。priceList はエクスポートされていないので、果物の値段は getPrice を使って求めることになります。
fruit1.hs では、モジュール Fruit をインポートして、関数 sumPrice を定義しています。sumPrice は getPrice を使ってリストに格納された果物の合計値を求める関数です。
それでは実行してみましょう。
ghci> :l fruit1
[1 of 2] Compiling Fruit ( Fruit.hs, interpreted )
[2 of 2] Compiling Main ( fruit1.hs, interpreted )
Ok, two modules loaded.
ghci> priceList
<interactive>:6:1: error: [GHC-88464]
Variable not in scope: priceList
ghci> :t Apple
Apple :: Fruit
ghci> getPrice Apple
Just 100
ghci> sumPrice [Apple, Grape, Grape, Orange, Orange, Orange]
1000
priceList はアクセスできませんが、getPrice で Apple の値段を求めることができます。最後に、sumPrice で合計値を求めています、
次は簡単なデータ構造の例題として「スタック (stack)」と「キュー (queue)」を取り上げます。最初にスタックの動作を説明します。次の図を見てください。
|-----| |[ A ]| |[ B ]| |[ A ]| |-----|
| | | |-----| |[ A ]| |-----| | | |
| | | | | | |-----| | | | | | |
| | | | | | | | | | | | | | |
| | | | | | | | | | | | | | |
+-----+ +-----+ +-----+ +-----+ +-----+
(1) 空の状態 (2) PUSH A (3) PUSH B (4) POP B (5) POP A
図 : スタックの動作例
上図は、バネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもう一つ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。一つ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。
この容器の動作が、スタックの動作なのです。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。
Haskell の場合、スタックはリストを使って簡単に実現することができます。データを追加するときはリストの先頭に追加し、データを取り出すときはリストの先頭から行うように操作を限定すると、それはスタックの動作と同じになります。
プログラムは次のようになります。
リスト : スタック module Stack ( Stack, emptyStack, singleton, push, pop, top, isEmptyStack ) where -- スタックの定義 data Stack a = S [a] deriving Show -- 空のスタック emptyStack :: Stack a emptyStack = S [] -- 要素が一つのスタックを作る singleton :: a -> Stack a singleton x = S [x] -- データの追加 push :: Stack a -> a -> Stack a push (S xs) x = S (x:xs) -- データの削除 pop :: Stack a -> (a, Stack a) pop (S []) = error "Empty Stack" pop (S (x:xs)) = (x, S xs) -- データの取得 top :: Stack a -> a top (S []) = error "Empty Stack" top (S (x:_)) = x -- スタックは空か isEmptyStack :: Stack a -> Bool isEmptyStack (S []) = True isEmptyStack (S _) = False
最初に data 宣言でスタック Stack a を定義します。スタックの本体はリストです。新しいスタックを生成するため、空のスタックを変数 emptyStack にセットします。関数 shigleton は引数 x を格納したスタックを返します。
スタックの操作関数は簡単です。push はデータをリストの先頭に追加します。pop はリストの先頭要素とそれを取り除いたスタックを返します。データの取得は関数 top で行います。スタックが空の場合、pop と top を適用することができないので、error でエラーを送出します。関数 isEmptyStack はスタックが空かチェックする述語です。
Haskell は純粋な関数型言語なので、スタックを破壊的に書き換えることはできません。push と pop は新しいスタックを返すことに注意してください。
簡単な使用例を示します。モジュール Stack.hs は ghci のコマンド :m でロードできなかったので、コマンド :l で Stack.hs を読み込んでいます。
ghci> :l Stack [1 of 1] Compiling Stack ( Stack.hs, interpreted ) Ok, one module loaded. ghci> a = push emptyStack 1 ghci> :t +d a a :: Stack Integer ghci> a S [1] ghci> singleton 1 S [1] ghci> b = push a 2 ghci> b S [2,1] ghci> c = push b 3 ghci> c S [3,2,1] ghci> top c 3 ghci> (x, d) = pop c ghci> x 3 ghci> d S [2,1] ghci> e = foldl push emptyStack [1..10] ghci> e S [10,9,8,7,6,5,4,3,2,1] ghci> isEmptyStack emptyStack True ghci> isEmptyStack d False
正常に動作していますね。純粋な関数型言語の場合、変数の値を書き換えることができないので、push や pop の返り値を別の変数に格納する必要があります。ご注意くださいませ。
次はキューについて説明します。キューは「待ち行列」といわれるデータ構造です。たとえばチケットを買う場合、窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。
このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造がキューなのです。キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。
先頭 最後尾
---------------------------
<= 1 2 3 4 5 . . . n <=
---------------------------
先頭 最後尾
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
queue ─→│・│・┼─→│・│・┼─→│・│・┼・・・→│・│／│
└┼┴─┘ └┼┴─┘ └┼┴─┘ └┼┴─┘
↓ ↓ ↓ ↓
１ ２ ３ ｎ
図 : キューの構造
キューにデータを入れることを enqueue といい、キューからデータを取り出すことを dequeue といいます。リストを使ってキューを実装する場合、上図のようにキューの先頭とリストの先頭を対応させます。すると、キューからデータを取り出すには、リストの先頭からデータを取り出すだけですみます。これはとても簡単ですね。
ただし、キューにデータを入れるには、リストの最後尾にデータを追加することになるため、ちょっとした工夫が必要になります。たとえば、データの追加に演算子 ++ を使うと、データを追加するたびにリスト（キュー）がコピーされてしまいます。このため、キューに格納されているデータが多くなると時間がかかるようになります。
これを回避する方法はいろいろ考えられるのですが、今回は SML/NJ や OCaml などの関数型言語で使われている方法を紹介します。次の図を見てください。
先頭
変数 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
front ─→│０│・┼─→│１│・┼─→│２│／│
└─┴─┘ └─┴─┘ └─┴─┘
最後尾
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
rear ─→│５│・┼─→│４│・┼─→│３│／│
└─┴─┘ └─┴─┘ └─┴─┘
図 : キューの構造（改良版）
上図は 2 つのリストでキューを表しています。データを取り出すときは front のリストを、データを追加するときは rear のリストを使います。front と rear で一つのキューを構成し、rear のリストはデータを逆順で格納することになります。ようするに、front が先頭で rear が最後尾になるわけです。上図のキューを一つのリストで表すと [0, 1, 2, 3, 4, 5] になります。
したがって、front が空リストでも rear にデータがあれば、キューは空ではありません。rear のリストを逆順にして front にセットし、rear を空リストにします。これで front からデータを取り出すことができます。キューが空の状態は front と rear が両方とも空リストの場合です。
それではプログラムを作りましょう。次のリストを見てください。
リスト : キューの実装 module Queue ( Queue, emptyQueue, singleton, enqueue, dequeue, front, isEmptyQueue ) where -- キューの定義 data Queue a = Q [a] [a] deriving Show -- 空のキュー emptyQueue :: Queue a emptyQueue = Q [] [] -- 要素が一つのキューを返す singleton :: a -> Queue a singleton x = Q [x] [] -- データの追加 enqueue :: Queue a -> a -> Queue a enqueue (Q front rear) x = Q front (x:rear) -- データの取り出し dequeue :: Queue a -> (a, Queue a) dequeue (Q [] []) = error "Empty Queue" dequeue (Q [] rear) = dequeue (Q (reverse rear) []) dequeue (Q (x:xs) rear) = (x, Q xs rear) -- 先頭データの参照 front :: Queue a -> a front (Q [] []) = error "Empty Queue" front (Q [] rear) = front (Q (reverse rear) []) front (Q (x:_) _) = x -- キューは空か isEmptyQueue :: Queue a -> Bool isEmptyQueue (Q [] []) = True isEmptyQueue (Q _ _) = False
まず data 宣言でデータ型 Queue a を定義します。データ構築子は Q [a] [a] で、第 1 要素が front で第 2 要素が rear になります。emptyQueue は空のキュー (Q [ ] [ ]) を表す変数です。関数 singleton は引数 x を格納したキューを返します。
関数 equeue はキューにデータ x を追加します。これは x を rear の先頭に追加するだけです。関数 dequeue はキューからデータを取り除きます。キューが空の場合は error でエラーを送出します。front が空リストの場合は、新しいキュー Q (reverse rear) [ ] を作って dequeue を再帰呼び出しします。front にデータがある場合は先頭要素を取り除くだけです。関数 front はキューの先頭要素を返します。処理は dequeue とほとんど同じで、違いは front の先頭データ x を返すだけです。関数 isEmptyQueue は、キューが空であれば True を、そうでなければ False を返します。
それでは簡単な実行例を示します。
ghci> :l Queue [1 of 1] Compiling Queue ( Queue.hs, interpreted ) Ok, one module loaded. ghci> a = enqueue emptyQueue 1 ghci> a Q [] [1] ghci> :t +d a a :: Queue Integer ghci> singleton 1 Q [1] [] ghci> b = enqueue a 2 ghci> b Q [] [2,1] ghci> c = enqueue b 3 ghci> c Q [] [3,2,1] ghci> front c 1 ghci> (x, d) = dequeue c ghci> x 1 ghci> d Q [2,3] [] ghci> (y, e) = dequeue d ghci> y 2 ghci> e Q [3] [] ghci> (z, f) = dequeue e ghci> z 3 ghci> f Q [] [] ghci> isEmptyQueue f True ghci> isEmptyQueue e False ghci> g = foldl enqueue emptyQueue [1..10] ghci> g Q [] [10,9,8,7,6,5,4,3,2,1] ghci> dequeue g (1,Q [2,3,4,5,6,7,8,9,10] [])
正常に動作していますね。
つぎの変数と関数を格納したモジュール Prime.hs を作成してください。
primes :: [Integer] isPrime :: Integer -> Bool factorization :: Integer -> [(Integer, Integer)]
モジュール Prime を使って次の数列を定義してください。
リスト : 解答例 (Prime.hs)
module Prime (primes, isPrime, factorization) where
isPrime :: Integer -> Bool
isPrime n = iter primes
where
iter (p:ps)
| p * p > n = True
| n `mod` p == 0 = False
| otherwise = iter ps
primesFrom :: Integer -> [Integer]
primesFrom n
| isPrime n = n : primesFrom (n + 2)
| otherwise = primesFrom (n + 2)
primes = 2 : 3 : 5 : primesFrom 7
factor :: Integer-> Integer -> Integer -> (Integer, Integer)
factor n m c
| n `mod` m /= 0 = (c, n)
| otherwise = factor (n `div` m) m (c + 1)
factorization :: Integer -> [(Integer, Integer)]
factorization n = iter primes n []
where
iter (p:ps) x a
| x == 1 = reverse a
| x < p * p = reverse ((x, 1) : a)
| otherwise = case factor x p 0 of
(0, _) -> iter ps x a
(c, m) -> iter ps m ((p, c) : a)
モジュール Prime.hs はコンパイルすると速くなります。
$ stack ghc -- -O -c -dynamic Prime.hs $ stack exec ghci GHCi, version 9.6.6: https://www.haskell.org/ghc/ :? for help ghci> :l Prime Ok, one module loaded. ghci> :show modules Prime ( Prime.hs, Prime.o ) ghci> take 25 primes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] ghci> isPrime (2^31 - 1) True ghci> isPrime (2^32 - 1) False ghci> factorization (2^31 - 1) [(2147483647,1)] ghci> factorization (2^32 - 1) [(3,1),(5,1),(17,1),(257,1),(65537,1)] ghci> fibo = 0 : 1 : zipWith (+) (tail fibo) fibo ghci> take 15 fibo [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377] ghci> fiboPrime = filter isPrime (drop 3 fibo) ghci> take 8 fiboPrime [2,3,5,13,89,233,1597,28657] ghci> twinPrime = filter (\(x, y) -> y - x == 2) $ zipWith (,) primes (tail primes) ghci> take 20 twinPrime [(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61),(71,73),(101,103),(107,109), (137,139),(149,151),(179,181),(191,193),(197,199),(227,229),(239,241),(269,271), (281,283),(311,313)]