Ix―Haskellでのインデックス演算

# Ix―Haskellでのインデックス演算

Haskellの主要なデータ構造/データの演算といえばリスト(`[a]`)、n-タプル(`(a, a)`)、マップ(`Map k a`)、集合(`Set a`)だと思いますが、ここでよく忘れられがちなのがインデックス演算(`Ix`)です。`Ix`クラスは配列的な構造を持ち、インデックス演算ができる型をそのインスタンスにしています。今回は、そんな`Ix`クラスについて解説します。

※この記事を書くのに使われているGHCのバージョンは8.8.3です。

## Ixのルーツ

Ixは、遅くともHaskell 98の標準ライブラリには含まれていたことがわかります。

> The `Ix` class is used to map a contiguous subrange of values in a type onto integers.  It is used primarily for array indexing (see Chapter [16](https://www.haskell.org/onlinereport/array.html#arrays)).

> `Ix`クラスは型の値の連続した部分範囲を整数の上に写像します。主に配列のインデックス付けに利用されます(チャプター16を参照)。

Haskellの前身のMirandaにはインデックス操作は見当たらなかったので、おそらく策定前から存在していたと考えられます。

## Ixクラス

では、`Ix`クラスを触ってみましょう。

```haskell
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`はペアからその範囲の配列を生成します。

```haskell
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から始まります)を与え、それが配列の長さを超えていれば例外を発生させます。

```haskell
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`で生成されたペアに引数の要素が含まれているか判定します。

```haskell
Prelude Data.Ix> inRange (1,5) 10
False
Prelude Data.Ix> inRange (1,5) 2
True
```

`rangeSize`は配列のサイズを`Int`で返します。

```haskell
Prelude Data.Ix> rangeSize (1,1000)
1000
Prelude Data.Ix> rangeSize ((-1000),1000)
2001
```

また、これらの関数の実装は以下の4つを満たす必要があります。

```haskell
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`クラスのインスタンスには、以下のような型があります。

```haskell
Word, Ordering, Integer, Int, Char, Bool, (),
(a, b), (a, b, c), (a, b, c, d), (a, b, c, d, e)
```

ただし、タプルの場合は中の値が全て`Ix`のインスタンスである必要があります。

## インスタンスの導出

`Ix`のインスタンスの導出は、直積型のうち値コントラクタを持たないものと、その値を含むタプルのみで可能です。例えば、次のような型があります。

```haskell
data SolarSystem = Mercury
                 | Venus
                 | Earth
                 | Mars
                 | Jupiter
                 | Saturn
                 | Uranus
                 | Neptune
                 deriving (Eq, Show, Ord)
```

この型は`Ix`クラスのインスタンスの型制約である`Ord`を自動導出しているため、そのまま`Ix`を自動導出してその関数群を使うことができます。

```haskell
*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つのルールを確かめてみましょう。

```haskell
-- 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はインデックス操作を行う
- 列挙できる型(型コンストラクタを持たない値のみで構成される直積型)と相性が良い

## 参考文献

- [Hackage - Data.Ix](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Ix.html)
- [The Haskell 98 Library Report: Indexing Operations](https://www.haskell.org/onlinereport/ix.html)
- [The Haskell 2010 Libraries - Chapter 19 Data.Ix](https://www.haskell.org/onlinereport/haskell2010/haskellch19.html)