계정: 로그인
AA 📝
13. 배열

A Gentle Introduction to Haskell, Version 98
이전 다음 위로


이상적으로 얘기하자면 함수형 언어에서의 배열이란 단지 인덱스에서 값으로의 함수로 간주될 뿐입니다만, 실용적 측면에서 보면 배열 원소에 효율적으로 접근하기 위해서는 정수의 유한하고 연속적인 부분집합으로 이루어진 이 함수의 정의역의 특성을 활용할 수 있어야합니다. 따라서 Haskell은 배열을 적용 연산을 갖는 일반적인 함수로 취급하지 않으며, 대신 subscript 연산을 갖는 추상 자료형으로 취급합니다.

함수형 배열에 대한 두 가지 주된 접근방법인 점증형(incremental) 정의와 고정형(monolithic) 정의에 대해서 고려해봅니다. 점증형의 경우, 주어진 크기의 빈 배열을 만드는 함수 하나와, 함수, 인덱스, 값 하나씩을 각각 받아서 기존 배열과는 주어진 인덱스에서만 다른 새로운 배열을 만드는 함수 하나를 얻게 됩니다. 명백히, 이런 식의 배열 의미론을 곧이곧대로 구현할 경우 그 결과물은 매 점증형 재정의 때마다 배열의 새로운 사본을 요구하거나 배열 참조에 있어서 선형 비례로 시간이 오래 걸리는 등 참을 수 없을 만큼 비효율적일겁니다. 따라서, 정말 심각하게 이런 접근방법을 실제로 사용하고자 한다면 과다한 복사를 피하기 위해 세련된 분석과 똑똑한 런타임 디바이스가 필요해집니다. 반면에 고정형 접근 방법에서는 배열의 중간 과정 값들을 참조하지 않고 배열 전체를 한꺼번에 구성합니다. Haskell에서는 점증형 배열 갱신 연산자가 있지만, 배열 관련 설비들의 주된 공략 목표는 고정형 접근 방식입니다.

배열은 Standard Prelude의 일부가 아닙니다 — 표준 라이브러리에 배열 연산자들이 들어있습니다. 배열을 사용하는 모든 모듈들은 반드시 Array 모듈을 수입해야만 합니다.

13.1 인덱스 타입

Ix 라이브러리는 배열 인덱스의 타입 클래스를 정의하고 있습니다:

   1 class  (Ord a) => Ix a  where
   2     range      :: (a,a) -> [a]
   3     index      :: (a,a) -> a -> Int
   4     inRange    :: (a,a) -> a -> Bool

Int, Integer, Char, Bool, 그리고 길이 5까지의 Ix의 튜플 타입에 대해서 인스턴스 선언이 제공됩니다; 게다가, 인스턴스들은 나열형 타입과 튜플 타입에 대해서 자동적으로 파생될 수 있습니다. 원시 타입은 벡터 인덱스로 간주하고, 튜플은 다차원 배열의 인덱스로 간주합니다. 클래스 Ix의 각각의 연산들의 첫번째 인수는 인덱스들의 쌍이라는 점에 주목하십시오; 이들은 전형적으로 배열의 경계(bound) (첫번째와 마지막 인덱스)입니다. 예를 들어, Int 인덱스를 갖고 0으로 시작하며 원소가 10개인 벡터의 경계는 (0,9)이고, 1로 시작하는 100×100 형렬의 경계는 ((1,1),(100,100))입니다. (다른 많은 언어들에서 이런 경계는 1:100, 1:100 같은 형태로 쓰이고 있지만, 지금 보여드린 형태가 타입 시스템에 더 잘 어울립니다. 각각의 경계는 일반적인 인덱스와 같은 타입이기 때문입니다.)

range 연산은 경계쌍 하나를 받아서 그 경계 사이에 들어있는 인덱스들의 리스트를 인덱스의 순서에 따라 정렬해서 만들어냅니다. 예를 들어,

술어 inRange는 인덱스가 주어진 경계 쌍 안쪽에 있는지를 알려줍니다. (튜플 타입에 대해서는, 이 테스트는 구성원소에 따라 수행됩니다.) 마지막으로, index 연산은 배열의 특정 원소의 위치를 가리키게 해줍니다: 경계 쌍과 경계 안쪽의 인덱스가 주어지면, 이 연산은 범위 내에서 인덱스의 0으로 시작하는 순서 값을 내줍니다. 예를 들어:

13.2 배열 생성

Haskell의 고정형 배열 생성 함수는 경계쌍과 인덱스-값 순서쌍의 리스트—즉, 결합 (association) 리스트—로부터 배열을 생성합니다:

예를 들어, 다음은 1부터 100까지 수들의 제곱의 배열의 정의입니다:

   1 squares    =  array (1,100) [(i, i*i) | i <- [1..100]]

이 배열 표현식은 list comprehension을 결합 리스트에 사용하는 전형적인 용법입니다; 사실, 이런 용법은 Id 언어 [6]의 array comprehensions과 비슷한 배열 표현식을 만들어냅니다.

배열 요소 참조(subscripting)는 중위 연산자 !에 의해 수행되며 배열의 경계는 함수 bounds를 이용해서 추출할 수 있습니다:

경계와 각각의 인덱스에 적용될 함수를 매개변수화함으로써 이 예제를 일반화시킬 수 있습니다:

   1 mkArray           :: (Ix a) => (a -> b) -> (a,a) -> Array a b
   2 mkArray f bnds    =  array bnds [(i, f i) | i <- range bnds]

따라서, squaresmkArray (\i -> i * i) (1,100)로 정의할 수 있습니다.

많은 배열들이 재귀적으로 정의됩니다; 즉, 다른 값에 의존하는 어떤 원소들의 값으로 정의됩니다. 예를 들어, 피보나치 수열을 리턴하는 함수는 다음과 같습니다:

   1 fibs      :: Int -> Array Int Int
   2 fibs n    =  a  where
   3     a    =  array (0,n) ([(0, 1), (1, 1)] ++
   4                          [(i, a!(i-2) + a!(i-1)) | i <- [2..n]])

이런 재귀의 또다른 예로는 n×n 파면 (wavefront) 행렬이 있으며, 이 행렬에서 첫 행과 첫 열의 값은 모두 1이고, 나머지 원소들은 그 원소의 왼쪽, 왼쪽위, 위쪽 원소들의 합입니다:

   1 wavefront      :: Int -> Array (Int,Int) Int
   2 wavefront n    =  a  where
   3     a    =  array ((1,1),(n,n))
   4                   ([((1,j), 1) | j <- [1..n]] ++
   5                    [((i,1), 1) | i <- [2..n]] ++
   6                    [((i,j), a!(i,j-1) + a!(i-1,j-1) + a!(i-1,j))
   7                                | i <- [2..n], j <- [2..n]])

병렬 구현물에서 이 재귀에 의해 첫행과 첫열에서 병렬적으로 계산이 시작되고 왼쪽 위로부터 오른쪽 아래를 향해 쐐기 모양의 파문을 일으키면서 계산이 진행되기 때문에 파면행렬 (wavefront matrix)이라고 불립니다. 하지만, 결합 리스트에는 계산 순서가 명시되어있지 않다는 점에 극히 주의하셔야 합니다.

지금까지의 예제들 각각에서, 각각의 인덱스마다, 그리고 배열 경계 안쪽에 있는 인덱스들에만 고유한 결합을 제공했었습니다. 그리고 사실상 완전하게 정의된 배열에 대해서도 일반적으로 이렇게 해야만 합니다. 경계를 벗어나는 인덱스를 갖는 결합은 오류를 유발합니다; 그러나, 만일 인덱스를 빠트리거나 같은 인덱스가 두 번 이상 나온다고 해서 즉시 오류가 나지는 않습니다. 대신, 그 인덱스 자리의 배열 값은 정의되지 않은 상태이며, 따라서 이런 인덱스를 가지고 배열을 참조하면 오류를 유발합니다.

13.3 축적 (Accumulation)

어떻게 하면 하나의 인덱스에 결합된 여러개의 값들을 묶을지를 명시함으로써, 결합 리스트에서 하나의 인덱스는 많아야 한 번 밖에 나올 수 없다는 제한을 완화시킬 수 있습니다. 그리고 이 결과물을 축적 배열(accumulated array)이라고 부릅니다:

accumArray의 첫번째 인수는 축적 함수이고, 두 번째 인수는 초기 값(배열의 각 원소에 대해서 마찬가지임)이며, 나머지 인수들은 array 함수에서처럼 경계와 결합 리스트입니다. 전형적으로, 축적 함수는 (+)이고 초기 값은 영입니다; 예를 들어, 아래 함수는 경계쌍 하나와 (인덱스 타입의) 값들의 리스트 하나를 받아서 도수분포표 하나를 내놓습니다. 즉, 경계 내의 각 값들이 등장하는 횟수의 표입니다:

   1 hist            :: (Ix a, Integral b) => (a,a) -> [a] -> Array a b
   2 hist bnds is    =  accumArray (+) 0 bnds [(i, 1) | i <- is, inRange bnds i]

구간 [a,b)에 대한 측량값들을 가지고 있고, 구간을 열 개로 나누어 각각의 구간들에 대한 측량값들을 얻고자 한다면:

   1 decades        :: (RealFrac a) => a -> a -> [a] -> Array Int Int
   2 decades a b    =  hist (0,9) . map decade  where
   3     decade x    =  floor ((x - a) * s)
   4     s           =  10 / (b - a)

13.4 점증형 (incremental) 갱신

고정형 배열 생성 함수 외에도, Haskell에는 중위 연산자 //로 표기되는 점증형 배열 갱신 함수가 있습니다; 가장 간단한 경우로서, 배열 a의 원소 iv로 갱신되는 것은 a // [(i, v)]라고 씁니다. 대괄호를 쓰는 이유는 (//)의 좌측 인수가 배열 인덱스들의 진부분집합을 포함하는 결합 리스트이기 때문입니다:

array 함수에서처럼, 결합 리스트의 인덱스들은 정의하려는 값들에 대해서 유일해야합니다. 예를 들어, 행렬의 두 행을 교환하는 함수는 다음과 같습니다:

   1 swapRows           :: (Ix a, Ix b, Enum b) => a -> a -> Array (a,b) c -> Array (a,b) c
   2 swapRows i i' a    =  a // ([((i ,j), a!(i',j)) | j <- [jLo..jHi]] ++
   3                             [((i',j), a!(i ,j)) | j <- [jLo..jHi]])  where
   4     ((iLo,jLo),(iHi,jHi))    =  bounds a

그러나, 여기서 같은 j 인덱스들의 리스트에 대한 두 개의 독립된 list comprehension들을 결합한 것은 약간 비효율적입니다. 이것은 마치 절차형 언어에서 하나면 될 루프를 두 개 쓴 것과 같습니다. 걱정하실 필요가 없는 것이, Haskell에서는 루프 결합 최적화에 해당하는 것을 수행할 수 있습니다:

   1 swapRows i i' a    =  a // [assoc | j     <- [jLo..jHi],
   2                                     assoc <- [((i ,j), a!(i',j)),
   3                                               ((i',j), a!(i, j))] ]  where
   4     ((iLo,jLo),(iHi,jHi))    =  bounds a

13.5 예제: 형렬 곱셈

명백히 일반적인 함수 정의에 대해 오버로딩을 할 수 있다는 장점이 있는 행렬 곱셈 예제를 통해 Haskell 배열에 대한 소개를 마칠까 합니다. 행렬 원소 타입에 대한 곱셈과 덧셈만이 관여되기 때문에, 그렇게되지 않도록 열심히 노력하지 않는 한, 어떠한 수치형 타입의 행렬이라도 곱할 수 있는 함수를 얻게됩니다. 게다가, 만일 인덱스에 대해 (!)Ix의 연산들만을 적용하려고 주의를 기울인다면, 인덱스 타입들에 대한 일반성을 얻게 되고, 사실상 행과 열의 네 가지 인덱스 타입들이 모두 같아야만할 필요는 없게됩니다. 하지만 문제를 단순화시키기 위해서, 좌항 행렬의 열 인덱스와 우항 행렬의 행 인덱스는 같은 타입이어야 하고, 게다가 그 경계까지도 같아야한다고 보겠습니다:

   1 matMult         :: (Ix a, Ix b, Ix c, Num d) =>
   2                    Array (a,b) d -> Array (b,c) d -> Array (a,c) d
   3 matMult x y     =  array resultBounds
   4                          [((i,j), sum [x!(i,k) * y!(k,j) | k <- range (lj,uj)])
   5                                        | i <- range (li,ui),
   6                                          j <- range (lj',uj') ]
   7         where ((li,lj),(ui,uj))         =  bounds x
   8               ((li',lj'),(ui',uj'))     =  bounds y
   9               resultBounds
  10                 | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))
  11                 | otherwise             = error "matMult: incompatible bounds"

여담이지만, accumArray를 사용해서 matMult를 정의할 수도 있으며, 결과적으로는 절차형 언어의 흔한 표현과 좀 더 비슷한 형태를 띄게됩니다:

   1 matMult x y     =  accumArray (+) 0 resultBounds
   2                               [((i,j), x!(i,k) * y!(k,j))
   3                                       | i <- range (li,ui),
   4                                         j <- range (lj',uj')
   5                                         k <- range (lj,uj)  ]
   6         where ((li,lj),(ui,uj))         =  bounds x
   7               ((li',lj'),(ui',uj'))     =  bounds y
   8               resultBounds
   9                 | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))
  10                 | otherwise             = error "matMult: incompatible bounds"

간단하게 sum(*)를 함수형 매개변수들로 바꿔서 함수를 higher-order로 만듦으로써 더더욱 일반화시킬 수 있습니다:

   1 genMatMult      :: (Ix a, Ix b, Ix c) =>
   2                    ([f] -> g) -> (d -> e -> f) ->
   3                    Array (a,b) d -> Array (b,c) e -> Array (a,c) g
   4 genMatMult sum' star x y  =
   5       array resultBounds
   6             [((i,j), sum' [x!(i,k) `star` y!(k,j) | k <- range (lj,uj)])
   7                                  | i <- range (li,ui),
   8                                    j <- range (lj',uj') ]
   9         where ((li,lj),(ui,uj))         =  bounds x
  10               ((li',lj'),(ui',uj'))     =  bounds y
  11               resultBounds
  12                 | (lj,uj)==(li',ui')    =  ((li,lj'),(ui,uj'))
  13                 | otherwise             = error "matMult: incompatible bounds"

APL 팬이라면 다음과 같은 함수들 얼마나 유용할지 알 수 있을겁니다:

이중 첫번째 것을 보면, 인수들은 수치 행렬들이고, 결과 행렬의 (i,j)번째 원소는 입력 행렬들의 i번째 행과 j번째 열의 해당되는 원소들의 최대 차이가 됩니다. 두번째 것의 경우에는, 인수들은 동치 비교가 가능한 타입의 행렬들이고, 결과 행렬은 만일 첫 인수의 i번째 행과 두번째 인수의 j번째 열이 벡터로서 같다면 (그리고 같은 경우에만) (i,j)번째 원소가 True가 되는 Boolean 행렬입니다.

genMatMult의 원소 타입들은 같을 필요가 없지만, 함수 매개변수 star에 적절한 타입이어야 한다는 사실에 주의하십시오. 첫 행렬의 열 인덱스 타입과 두번째 행렬의 행 인덱스 타입이 같아야한다는 요구조건을 빼버림으로써 좀 더 일반화시킬 수 있습니다; 분명히, 두 행렬들은 첫번째 것의 열 길이와 두번째 것의 행 길이가 같기만 하다면 적절하다고 생각할 수 있습니다. 독자들 중에는 이렇게 훨씬 더 일반화된 버전을 유도해보고 싶은 분도 계실겁니다. (힌트: 길이를 재려면 index 연산을 사용하십시오.)


이전 다음 위로
A Gentle Introduction to Haskell, Version 98

Copyright © 1999 Paul Hudak, John Peterson and Joseph Fasel

Permission is hereby granted, free of charge, to any person obtaining a copy of “A Gentle Introduction to Haskell” (the Text), to deal in the Text without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Text, and to permit persons to whom the Text is furnished to do so, subject to the following condition: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Text.