Haskell을 사용하면서 리스트를 사용하지 않는 경우는 거의 없다고 볼 수 있다.
리스트는 다루기 쉽고 강력한 자료 구조이지만, 만능은 아니다.
특히나 함수형 언어는 성능이 떨어진다고 비판을 받고는 하는데, 리스트는 그 구조 때문에 함수형 언어와 관계없이 느리다.
그러므로 성능이 신경 쓰인다면 리스트의 특성을 잘 이해하고서 사용해야 한다.
그 한 가지 예로서, 리스트를 다룰 때 자주 사용하는 함수 중 하나인 length를 살펴보자.
Definition of length
함수 length는 주어진 리스트의 길이를 재는 함수이다.
Haskell의 리스트는 길이 정보를 별도로 저장하지 않는 단순한 구현이다.
그도 그럴 것이 지연 계산법의 특성상, 리스트의 길이가 얼마나 될지는 그 리스트가 주어진 시점에서는 알 수 없기 때문이다.
거기에 무한 리스트도 당연하다시피 다루고 있는데, 리스트의 길이를 미리 파악할 수 없는 이상, 길이 정보가 리스트에 포함되지 않는 것은 당연하다고 볼 수 있다.
하지만 리스트의 길이는 자주 사용할 일이 있으니까 재어 볼 필요는 있고, 그를 위해서 length함수가 존재한다.
그런데 이 length 함수로 길이를 재는 것이 비효율적이거나, 불가능한 경우가 있다.
length 함수의 구현은 매우 단순해서, 앞에서부터 하나하나 세어가는 재귀함수이다.
최신 버전의 length는 다음과 같이 구현되어 있다.
length :: t a -> Int length = foldl' (\c _ -> c+1) 0
이 구현은 옛 버전에 비해서 일반화되었다1.
초심자가 읽고서 이해하기 힘든 괴기 무쌍한 정의인지라, 좀 더 옛날의 정의를 살펴보자.
length :: [a] -> Int
length l = len l 0#
where
len :: [a] -> Int# -> Int
len [] a# = I# a#
len (_:xs) a# = len xs (a# +# 1#)
이건 최적화를 위해 몇 가지 손을 본 구현인데, 이건 copy & paste 해도 동작하지 않는다.2
최적화된 부분을 복원(…)하면 다음과 같다.
length :: [a] -> Int
length l = len l 0
where
len [] a = a
len (_:xs) a = len xs (a + 1)
즉, 리스트의 요소를 하나하나 세어가면서 길이를 재는 것이다.
이것만 보면 당연하고 의심할 바 없는 정의이지만, 이게 문제가 되는 경우가 많다는 것이다.
언제 문제가 될까?
이 length 함수를 손쉽게 사용할 때 일어날 수 있는 잠재적인 문제점들은 매우 많다.
이 글에서는 지연 계산법에 관한 부분은 간단히 언급만 하고, 연산량에 관련된 부분만을 살펴보기로 하자.
Case 1: 지연 계산법 (lazy evaluation)
먼저, 지연 계산법에 관련된 부분이다.
다음과 같은 조건을 살펴보자.
if length [1..] == 1 then ... else ...
이건 당연히 False이지만, 리스트의 길이가 무한하고, length 함수는 그 리스트를 무한히 따라가기 때문에 정지하지 않는다.
이 외에도 계산할 필요가 없어서 error를 발생시킬 필요가 없는데, length 함수를 사용해서 error를 발생시키는 경우가 있다.
사실 이 지연 계산법에 관한 부분을 더 깊게 다루어야 하지만, 상당히 길어지고 length함수만이 관련된 것도 아니기에 다른 글에서 다루도록 하겠다.
Case 2: 연산량 문제 – 길이가 1인지 아닌지만 확인하고 싶은데
length 함수는 if의 조건문 안에서 자주 사용하게 된다.
이를테면 일직선 상에 있는 바위의 위치가 들어있는 리스트를 받으면 그 바위 간의 거리를 돌려주는 함수를 생각해보자.
머리를 잘 쓰면 다음과 같은 구현을 작성하지 않고 훨씬 더 보기 좋게 만들 수 있지만, 초심자가 쓸 것 같이 써봤다.
getDistances list
| null list = [] -- (1)
| length list == 1 = [] -- (2)
| otherwise = (second - first) : getDistances (tail list) -- (3)
where
first = head list
second = head (tail list)
이 함수의 구현 자체에는 아무런 문제도 없다.
하지만 조건문을 하나하나 자세히 살펴보면 문제가 있다는 것을 알 수 있다.
먼저, (1)은 아무런 문제가 없다.
null 함수는 빈 리스트인지 아닌지를 확인하는 함수로, O(1)의 엄청나게 싼 연산이다.
(2)는 잠시 내버려두고 (3)을 살펴보자.
where 안에서 정의한 것을 몇 개 사용하고 있지만, (3)도 전부 O(1)의 엄청나게 싼 연산이다.
문제는, (2)의 조건문 length list == 1이다.
length 함수는 그 구현을 보면 알겠지만, O(n)이다. (n은 리스트의 길이)
getDistances 함수는 (2)번 조건문에서 length 함수를 n번 불러내기 때문에, 결과적으로 getDistances의 연산량은 O(n^2)가 된다.
간단한 함수가 말도 안 되는 연산량을 가지게 된 것이다.
물론 getDistances의 구현 자체를 바꾸어버리면 되지만, 이번에는 length의 문제를 살펴보는 게 목적이니까 내버려두자.
자, 생각해보면 어떤 리스트의 길이가 1인지 아닌지를 살펴보는 것은 역시 상당히 싼 연산일 것이 분명하다.
그렇다면, 어떤 리스트의 길이가 주어진 길이인지 아닌지만 살펴보는 함수를 만들면 될 것 갈다.
길이를 측정하는 함수 isLength
isLength 함수를 다음과 같이 구현해보았다.
isLength [] 0 = True -- (1) isLength [] _ = False -- (2) isLength _ 0 = False -- (3) isLength list len = isLength (tail list) (len-1) -- (4)
이 함수의 연산량은 O(min(n,len))이다. 위의 getDistances에서 사용하는 경우에는 당연히 O(1)이다.
(3)은 없어도 동작하지만, 매우 긴 리스트가 올 경우를 생각하면 O(n)이 되기 때문에 있어야 한다.
isLength를 사용한 getDistances
getDistances list
| null list = [] -- (1)
| isLength list 1 = [] -- (2)
| otherwise = (second - first) : getDistances (tail list) -- (3)
where
first = head list
second = head (tail list)
당연하지만, 거의 바뀐 점이 없다.
하지만 length 대신에 isLength를 사용한 것 때문에 연산량은 O(n^2)에서 O(n)으로 획기적으로 줄어들었다.
Conclusion 1
기본적으로 제공되는 함수라고 하더라도 꼭 그 함수가 어떻게 구현되었는지 살펴보자.
Hackage에서 받은 라이브러리라면, 그 구현을 쉽게 찾아볼 수 있다. 하나하나 책갈피도 잘 달려있으니까 소스 코드를 검색할 필요도 없다.
Appendix 1: getDistances의 다른 구현을 생각해보자.
더 나은 구현이 있다고 주장했으니까, 예를 하나 정도 들어야 할 것 같다.
일단 간략한 구현의 예를 들어보자.
Trial 1: use pattern matching
Pattern matching을 사용하면 길이를 잴 필요가 없다.
다음은, getDistances를 pattern matching을 사용해서 그대로 옮겨놓은 구현이다.
getDistances' [] = [] getDistances' (_:[]) = [] getDistances' (x:y:zs) = (y - x) : getDistances' (y:zs)
Trial 2: one more step
getDistances'를 살펴보면 알겠지만, 위에서부터 두 개의 조건은 한 개로 합칠 수 있다.
고쳐 써보면 다음과 같다.
getDistances'' (x:y:zs) = (y - x) : getDistances'' (y:zs) getDistances'' _ = []
확인해보면 잘 동작한다.
Question 1: 새로운 구현 getDistances''와 length를 개선한 본래의 getDistances, 어느 쪽이 더 성능이 좋을까?
getDistances''의 구현은 간단하고 보기 좋지만(?), 하나 걱정되는 부분이 있다.
문제는 patttern matching의 비용이 얼마나 되는지 잘 모르겠다는 것이다.
특히나 이건 컴파일러와 그 최적화 방법에 따라서 바뀔 수 있는 부분이기에 항상 맞아들어가지는 않는다.
criterion으로 측정해보면, 그렇게 큰 차이는 없지만, pattern matching을 사용하는 getDistances''가 getDistances보다 조금 더 빠르다. 측정 오차 수준은 아니지만, 유의미한 수준이기는 하다. 다만 아주 조금 빠르다.
Appendix 2: 비교 함수를 만들어보자.
isLength는 길이가 딱 얼만큼인가만 확인할 수 있다.
하지만 당연하게도 길이가 더 긴지 짧은지를 확인하고 싶은 경우도 있다.
더 긴지 확인하는 경우와 짧은지를 확인하는 경우의 경계 조건이 미묘하게 다르지만, 그 정도는 모두 알고 있을 테니까 isShorter의 경우만 소개한다.
isShorter _ 0 = False isShorter [] _ = True isShorter list n = isShorter (tail list) (n-1)
실제로 사용할때는 주어진 길이가 음수인지를 확인한다든지, 인수를 정격(strict)화 한다든지 몇 가지 간단한 최적화를 할 필요가 있다.