Ix―Haskellでのインデックス演算
Haskellの主要なデータ構造/データの演算といえばリスト([a])、n-タプル((a, a))、マップ(Map k a)、集合(Set a)だと思いますが、ここでよく忘れられがちなのがインデックス演算(Ix)です。Ixクラスは配列的な構造を持ち、インデックス演算ができる型をそのインスタンスにしています。今回は、そんなIxクラスについて解説します。
※この記事を書くのに使われているGHCのバージョンは8.8.3です。
Ixのルーツ
Ixは、遅くともHaskell 98の標準ライブラリには含まれていたことがわかります。
The
Ixclass is used to map a contiguous subrange of values in a type onto integers. It is used primarily for array indexing (see Chapter 16).
Ixクラスは型の値の連続した部分範囲を整数の上に写像します。主に配列のインデックス付けに利用されます(チャプター16を参照)。
Haskellの前身のMirandaにはインデックス操作は見当たらなかったので、おそらく策定前から存在していたと考えられます。
Ixクラス
では、Ixクラスを触ってみましょう。
class Ord a => Ix a where
range :: (a, a) -> [a]
index :: (a, a) -> a -> Int
inRange :: (a, a) -> a -> Bool
rangeSize :: (a, a) -> Int
rangeはペアからその範囲の配列を生成します。
Prelude Data.Ix> range (1, 10)
[1,2,3,4,5,6,7,8,9,10]
Prelude Data.Ix> range ((-10), 10)
[-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10]
Prelude Data.Ix> range (0,(-1))
[]
indexは先ほどのrangeにインデックスの情報(0から始まります)を与え、それが配列の長さを超えていれば例外を発生させます。
Prelude Data.Ix> index (1,5) 3
2
Prelude Data.Ix> index (1,5) 10
*** Exception: Ix{Integer}.index: Index (10) out of range ((1,5))
inRangeはrangeで生成されたペアに引数の要素が含まれているか判定します。
Prelude Data.Ix> inRange (1,5) 10
False
Prelude Data.Ix> inRange (1,5) 2
True
rangeSizeは配列のサイズをIntで返します。
Prelude Data.Ix> rangeSize (1,1000)
1000
Prelude Data.Ix> rangeSize ((-1000),1000)
2001
また、これらの関数の実装は以下の4つを満たす必要があります。
inRange (l,u) i == elem i (range (l,u))
range (l,u) !! index (l,u) i == i -- when inRange (l,u) i
map (index (l,u)) (range (l,u))) == [0..rangeSize (l,u)-1]
rangeSize (l,u) == length (range (l,u))
Ixのインスタンス
Ixクラスのインスタンスには、以下のような型があります。
Word, Ordering, Integer, Int, Char, Bool, (),
(a, b), (a, b, c), (a, b, c, d), (a, b, c, d, e)
ただし、タプルの場合は中の値が全てIxのインスタンスである必要があります。
インスタンスの導出
Ixのインスタンスの導出は、直積型のうち値コントラクタを持たないものと、その値を含むタプルのみで可能です。例えば、次のような型があります。
data SolarSystem = Mercury
| Venus
| Earth
| Mars
| Jupiter
| Saturn
| Uranus
| Neptune
deriving (Eq, Show, Ord)
この型はIxクラスのインスタンスの型制約であるOrdを自動導出しているため、そのままIxを自動導出してその関数群を使うことができます。
*Main> range (Earth, Uranus)
[Earth,Mars,Jupiter,Saturn,Uranus]
*Main> index (Venus, Jupiter) Earth
1
*Main> inRange (Mars, Uranus) Venus
False
*Main> rangeSize (Mercury, Neptune)
8
ためしにこの型で、先ほどの4つのルールを確かめてみましょう。
-- inRange (l,u) i == elem i (range (l,u))
*Main> inRange (Mercury, Neptune) Earth
True
*Main> elem Earth (range (Mercury, Neptune))
True
-- range (l,u) !! index (l,u) i == i -- when inRange (l,u) i
*Main> range (Venus, Jupiter) !! index (Venus, Jupiter) Mars
Mars
-- map (index (l,u)) (range (l,u))) == [0..rangeSize (l,u)-1]
*Main> map (index (Earth, Saturn)) (range (Earth, Saturn))
[0,1,2,3]
*Main> [0..(rangeSize (Earth, Saturn) - 1)]
[0,1,2,3]
-- rangeSize (l,u) == length (range (l,u))
*Main> rangeSize (Jupiter, Neptune)
4
*Main> length (range (Jupiter, Neptune))
4
すべて満たしていますね。
まとめ
- Ixはインデックス操作を行う
- 列挙できる型(型コンストラクタを持たない値のみで構成される直積型)と相性が良い