Data.Array
Data.Array
Data.Array 모듈은 불변(immutable)하고 비엄격(non-strict)한 배열 타입을 제공해요. 이 모듈은 Data.Ix 모듈의 내용도 함께 다시 내보내요.
본문
14.1 불변·비엄격 배열 (Immutable non-strict arrays)
Haskell은 인덱스 가능한 배열(indexable arrays) 을 제공해요. 배열은 정의역이 정수의 연속 부분집합과 동형(isomorphic)인 함수로 생각할 수 있어요. 이런 방식으로 제한된 함수는 효율적으로 구현될 수 있고, 특히 프로그래머는 구성 요소(component)에 빠르게 접근할 수 있으리라 합리적으로 기대할 수 있어요. 이런 구현을 가능하게 하기 위해 배열은 일반 함수가 아니라 데이터로 취급돼요.
대부분의 배열 함수가 Ix 클래스에 관여하므로, 편의상 Data.Ix 모듈의 내용이 Data.Array에서 다시 내보내져요:
module Data.Ix
data Ix i => Array i e
인덱스가 i, 요소가 e인 불변·비엄격(boxed) 배열 타입이에요.
instance Ix i => Functor (Array i)
instance (Ix i, Eq e) => Eq (Array i e)
instance (Ix i, Ord e) => Ord (Array i e)
instance (Ix a, Read a, Read b) => Read (Array a b)
instance (Ix a, Show a, Show b) => Show (Array a b)
14.2 배열 생성 (Array construction)
array :: Ix i => (i, i) -> [(i, e)] -> Array i e
(i, i)는 경계(bounds) 의 쌍으로, 각각 배열의 인덱스 타입이에요. 이 경계들은 각각 배열에서 가장 낮은 인덱스와 가장 높은 인덱스(순서대로)를 뜻해요. 예를 들어 1부터 시작하는 길이 10인 벡터는 경계가 (1,10)이고, 1부터 시작하는 10×10 행렬은 경계가 ((1,1),(10,10))이에요.
[(i, e)]는 (인덱스, 값) 형태의 연관(associations) 리스트예요. 보통 이 리스트는 리스트 내포(list comprehension)로 표현돼요. 연관 (i, x)는 배열의 인덱스 i에 있는 값을 x로 정의해요.
지정된 경계를 가진 배열을 만들고, 그 경계 안의 주어진 인덱스들에 값을 담아요. 리스트 안의 어떤 인덱스가 경계를 벗어나면 배열은 정의되지 않음(undefined, 즉 bottom)이 돼요. 리스트 안에 같은 인덱스를 가진 연관이 두 개 있으면 그 인덱스의 값은 정의되지 않음(bottom)이 돼요.
인덱스를 이런 오류에 대해 검사해야 하므로, array는 경계 인자(argument)와 연관 리스트의 인덱스에 대해서는 엄격(strict)하지만 값에 대해서는 비엄격(non-strict)이에요. 따라서 다음과 같은 점화식(recurrence)이 가능해요:
a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])
배열 경계 안의 모든 인덱스가 연관 리스트에 등장해야 하는 건 아니지만, 등장하지 않는 인덱스와 연관된 값은 정의되지 않음(bottom)이 돼요. 어떤 차원에서든 하한(lower bound)이 상한(upper bound)보다 크면 배열은 유효하지만 비어 있어요. 빈 배열을 인덱싱하면 항상 배열 경계 오류가 나지만, bounds는 여전히 배열이 만들어진 경계를 돌려줘요.
listArray :: Ix i => (i, i) -> [e] -> Array i e
경계의 쌍과 인덱스 순서대로 된 값의 리스트로 배열을 만들어요.
accumArray :: Ix i => (e -> a -> e) -- 누적 함수(accumulating function)
-> e -- 초기 값(initial value)
-> (i, i) -- 배열의 경계
-> [(i, a)] -- 연관 리스트
-> Array i e
accumArray 함수는 연관 리스트에서 반복되는 인덱스를 누적 함수를 사용해 처리해요. 누적 함수는 같은 인덱스를 가진 연관들의 값을 결합해요. 예를 들어, 어떤 인덱스 타입의 값 리스트가 주어졌을 때, hist는 지정된 범위 안에서 각 인덱스의 발생 횟수의 히스토그램을 만들어요:
hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]
누적 함수가 엄격하면 accumArray는 연관 리스트의 값뿐 아니라 인덱스에 대해서도 엄격해요. 따라서 일반적인 array로 만든 배열과 달리, 누적 배열(accumulated array)은 일반적으로 재귀적이어서는 안 돼요.
14.3 배열 접근 (Accessing arrays)
(!) :: Ix i => Array i e -> i -> e
배열에서 주어진 인덱스의 값이에요.
bounds :: Ix i => Array i e -> (i, i)
배열이 만들어진 경계예요.
indices :: Ix i => Array i e -> [i]
배열의 인덱스 리스트를 오름차순으로 돌려줘요.
elems :: Ix i => Array i e -> [e]
배열의 요소 리스트를 인덱스 순서대로 돌려줘요.
assocs :: Ix i => Array i e -> [(i, e)]
배열의 연관 리스트를 인덱스 순서대로 돌려줘요.
14.4 배열의 점진적 갱신 (Incremental array updates)
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
첫 번째 인자와 동일하되, 오른쪽 인자의 연관들로 갱신된 배열을 만들어요. 예를 들어 m이 1부터 시작하는 n×n 행렬이라면, m//[((i,i), 0) | i <- [1..n]]은 대각선만 0으로 만든 같은 행렬이에요. 연관 리스트에서 반복되는 인덱스는 array에서처럼 처리돼요: 그 결과 배열은 정의되지 않음(bottom)이 돼요.
accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
accum f는 배열과 연관 리스트를 받아, 누적 함수 f로 리스트의 쌍들을 배열 안에 누적해요. 따라서 accumArray는 accum으로 정의할 수 있어요:
accumArray f z b = accum f (array b [(i, z) | i <- range b])
14.5 파생 배열 (Derived arrays)
ixmap :: (Ix i, Ix j) => (i, i) -> (i -> j) -> Array j e -> Array i e
ixmap은 배열 인덱스에 변환을 적용할 수 있게 해줘요. 원래 배열이 구현하고 있는 매핑의 오른쪽에 함수 합성을 제공하는 것으로 생각할 수 있어요. 배열 값의 유사한 변환은 Functor 클래스의 Array 인스턴스에서 fmap을 사용해 얻을 수 있어요.
14.6 명세 (Specification)
module Array ( module Data.Ix, -- export all of Data.Ix
Array, array, listArray, (!), bounds, indices, elems,
assocs, accumArray, (//), accum, ixmap
) where
import Data.Ix
import Data.List( (\\) )
infixl 9 !, //
data (Ix a) => Array a b = MkArray (a,a) (a -> b) deriving ()
array :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
array b ivs
| any (not . inRange b . fst) ivs = error "Data.Array.array: out-of-range array association"
| otherwise = MkArray b arr
where arr j = case [ v | (i,v) <- ivs, i == j ] of
[v] -> v
[] -> error "Data.Array.!: undefined array element"
_ -> error "Data.Array.!: multiply defined array element"
listArray :: (Ix a) => (a,a) -> [b] -> Array a b
listArray b vs = array b (zipWith (\ a b -> (a,b)) (range b) vs)
(!) :: (Ix a) => Array a b -> a -> b
(!) (MkArray _ f) = f
bounds :: (Ix a) => Array a b -> (a,a)
bounds (MkArray b _) = b
indices :: (Ix a) => Array a b -> [a]
indices = range . bounds
elems :: (Ix a) => Array a b -> [b]
elems a = [a!i | i <- indices a]
assocs :: (Ix a) => Array a b -> [(a,b)]
assocs a = [(i, a!i) | i <- indices a]
(//) :: (Ix a) => Array a b -> [(a,b)] -> Array a b
a // new_ivs = array (bounds a) (old_ivs ++ new_ivs)
where old_ivs = [(i,a!i) | i <- indices a, i `notElem` new_is]
new_is = [i | (i,_) <- new_ivs]
accum :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
accum f = foldl (\a (i,v) -> a // [(i,f (a!i) v)])
accumArray :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
accumArray f z b = accum f (array b [(i,z) | i <- range b])
ixmap :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c
ixmap b f a = array b [(i, a ! f i) | i <- range b]
instance (Ix a) => Functor (Array a) where
fmap fn (MkArray b f) = MkArray b (fn . f)
instance (Ix a, Eq b) => Eq (Array a b) where
a == a' = assocs a == assocs a'
instance (Ix a, Ord b) => Ord (Array a b) where
a <= a' = assocs a <= assocs a'
instance (Ix a, Show a, Show b) => Show (Array a b) where
showsPrec p a = showParen (p > arrPrec) (
showString "array " .
showsPrec (arrPrec+1) (bounds a) . showChar ' ' .
showsPrec (arrPrec+1) (assocs a) )
instance (Ix a, Read a, Read b) => Read (Array a b) where
readsPrec p = readParen (p > arrPrec)
(\r -> [ (array b as, u)
| ("array",s) <- lex r,
(b,t) <- readsPrec (arrPrec+1) s,
(as,u) <- readsPrec (arrPrec+1) t ])
-- Precedence of the 'array' function is that of application itself
arrPrec = 10