The Haskell 98 Report
top | back | next | contents | function index

15  インデックス演算


module Ix ( Ix(range, index, inRange, rangeSize) ) where

class  Ord a => Ix a  where
    range       :: (a,a) -> [a]
    index       :: (a,a) -> a -> Int
    inRange     :: (a,a) -> a -> Bool
    rangeSize   :: (a,a) -> Int

instance                   Ix Char      where ...
instance                   Ix Int       where ...
instance                   Ix Integer   where ...
instance  (Ix a, Ix b)  => Ix (a,b)     where ...
-- et cetera
instance                   Ix Bool      where ...
instance                   Ix Ordering  where ...

Ix クラスはある型の値の連続した部分範囲を整数の上に写像する のに用いられる。このクラスは主に配列のインデックスとして用いられる (16 節を見よ)。Ix クラスは メソッド range、index および inRange を含む。index 演算は、範囲の下界と上界を定義する境界の組と 添字を整数に写像する。range 演算はすべての添字を列挙する。 inRange 演算はある特定の添字が境界の組で定義された範囲の中に 入っているかどうかを判定する。

実装はこれらの演算について以下のような法則を仮定して良いことになって いる。

   range (l,u) !! index (l,u) i == i   -- when i is in range
   inRange (l,u) i == i `elem` range (l,u)
   map index (range (l,u))      == [0..rangeSize (l,u)]

15.1  Ix インスタンスの導出

data 宣言上の deriving 節を利用すると、自動的に Ix インスタンスを導出することができる (4.3.3 節)。このように導出 された Ix クラスに対するインスタンス宣言は列挙型(すなわち、 無引数の構成子でのみ構成されているデータ型)、および、単一構成子の データ型(これにはその構成要素が Ix のインスタンスである ような任意の大きなタプルも含まれる)に対してのみ可能である。 Haskell の実装は少なくともサイズ 15 までのタプルについて、Ix インスタンスを提供しなければならない。


instance  (Ix a, Ix b)  => Ix (a,b) where
        range ((l,l'),(u,u'))
                = [(i,i') | i <- range (l,u), i' <- range (l',u')]
        index ((l,l'),(u,u')) (i,i')
                =  index (l,u) i * rangeSize (l',u') + index (l',u') i'
        inRange ((l,l'),(u,u')) (i,i')
                = inRange (l,u) i && inRange (l',u') i'

-- Instances for other tuples are obtained from this scheme:
--
--  instance  (Ix a1, Ix a2, ... , Ix ak) => Ix (a1,a2,...,ak)  where
--      range ((l1,l2,...,lk),(u1,u2,...,uk)) =
--          [(i1,i2,...,ik) | i1 <- range (l1,u1),
--                            i2 <- range (l2,u2),
--                            ...
--                            ik <- range (lk,uk)]
--
--      index ((l1,l2,...,lk),(u1,u2,...,uk)) (i1,i2,...,ik) =
--        index (lk,uk) ik + rangeSize (lk,uk) * (
--         index (lk-1,uk-1) ik-1 + rangeSize (lk-1,uk-1) * (
--          ...
--           index (l1,u1)))
--
--      inRange ((l1,l2,...lk),(u1,u2,...,uk)) (i1,i2,...,ik) =
--          inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
--              ... && inRange (lk,uk) ik

Ix インスタンスの導出

15.2  Ix ライブラリ


module Ix ( Ix(range, index, inRange, rangeSize) ) where

class  Ord a => Ix a  where
    range     :: (a,a) -> [a]
    index     :: (a,a) -> a -> Int
    inRange   :: (a,a) -> a -> Bool
    rangeSize :: (a,a) -> Int

    rangeSize b@(l,h) | null (range b) = 0
                      | otherwise      = index b h + 1 
-- NB: replacing "null (range b)" by  "not (l <= h)"
-- fails if the bounds are tuples.  For example,
--  (1,2) <= (2,1)
-- but the range is nevertheless empty
-- range ((1,2),(2,1)) = []

instance  Ix Char  where
    range (m,n) = [m..n]
    index b@(c,c') ci
        | inRange b ci  =  fromEnum ci - fromEnum c
        | otherwise     =  error "Ix.index: Index out of range."
    inRange (c,c') i    =  c <= i && i <= c'

instance  Ix Int  where
    range (m,n) = [m..n]
    index b@(m,n) i
        | inRange b i   =  i - m
        | otherwise     =  error "Ix.index: Index out of range."
    inRange (m,n) i     =  m <= i && i <= n

instance  Ix Integer  where
    range (m,n) = [m..n]
    index b@(m,n) i
        | inRange b i   =  fromInteger (i - m)
        | otherwise     =  error "Ix.index: Index out of range."
    inRange (m,n) i     =  m <= i && i <= n

instance (Ix a,Ix b) => Ix (a, b) -- as derived, for all tuples
instance Ix Bool                  -- as derived
instance Ix Ordering              -- as derived
instance Ix ()                    -- as derived

The Haskell 98 Report
top | back | next | contents | function index
December 2002