5장 리스트 컴프리헨션

제네레이터

수학에서 컴프리헨션(comprehension)은 어떤 집합에서 새로운 집합을 만드는 것을 말한다. 예를 들어 ${\{x^2|x\in\{1..5\}}\}$는 집합 $\{1..5\}$에 있는 모든 원소를 제곱한 것을 원소로 갖는 새로운 집합 $\{1,4,9,16,25\}$를 의미한다. 하스켈에서도 비슷한 방법으로 리스트에서 리스트를 만들 수 있다.

ghci> [x^2 | x <- [1..5]]
[1,4,9,16,25]

표현식 x <- [1..5]를 제네레이터(generator)라고 한다. 리스트 컴프리헨션에서 제네레이터는 여러 개 쓸 수 있다. 제네레이터끼리는 쉼표로 구분한다. 예를 들어 두 리스트 [1,2,3]과 [4,5]의 모든 원소의 순서쌍을 아래처럼 만들 수 있다.

ghci> [(x,y) | x <- [1,2,3], y <- [4,5]]
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]

제네레이터 순서를 바꿔도 같은 순서쌍을 얻을 수 있긴 한데 순서가 조금 달라진다.

ghci> [(x,y) | y <- [4,5], x <- [1,2,3]]
[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]

나중에 적는 제네레이터는 먼저 적은 제네레이터 변수에 영향을 받는다. 예를 들어 리스트 [1..3]으로 만들 수 있는 모든 순서쌍을 아래처럼 만들 수 있다.

ghci> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]

이걸 이용하면 라이브러리 함수 concat도 아래처럼 구현할 수 있다. concat은 리스트 안에 든 여러 리스트를 이어 붙이는 함수이다.

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

리스트에서 필요 없는 원소를 버릴 때 와일드카드(wildcard) 패턴을 쓸 수 있다. 예를 들어 순서쌍 리스트에서 순서쌍의 첫 번째 원소만 갖는 리스트를 아래처럼 만들 수 있다.

firsts :: [(a,b)] -> [a]
firsts ps = [x | (x,_) <- ps]

리스트의 길이를 구하는 라이브러리 함수 length는 아래처럼 원소를 모두 1로 바꿔서 더하는 방법으로 구현할 수 있다.

length :: [a] -> Int
length x = sum [1 | _ <- xs]

여기서 제네레이터 _ <- xs는 원소의 개수만큼 숫자 1을 만들어 낸다.

가드

리스트 컴프리헨션에서는 가드(guards)라고 하는 논리 표현식을 써서 제네레이터에서 나온 값을 걸러 낼 수 있다. 가드가 참이면 그 값을 결과에 포함시키고 그렇지 않으면 버리는 식이다. 예를 들어 [x | x <- [1..10], even x]의 결과는 [1..10]의 모든 원소 중 짝수만 고른 [2,4,6,8,10]이다.

어떤 수의 약수를 구하는 방법은 아래와 같다.

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

ghci> factors 15
[1,3,5,15]

ghci> factors 7
[1,7]

약수가 1과 자기 자신 뿐인 수를 소수(prime)라고 한다. 함수 factors를 이용해서 어떤 수가 소수인지 아닌지 확인하는 함수를 아래처럼 정의할 수 있다.

prime :: Int -> Bool
prime n = factors n == [1,n]

ghci> prime 15
False

ghci> prime 7
True

15가 소수인지 판단할 때 약수를 끝까지 모두 구할 필요는 없다. lazy 평가에서는 1 외에 다른 약수가 나오거나 자기 자신이 나오는 순간 False가 리턴된다.

함수 prime을 이용하면 인자로 입력한 값보다 작은 모든 소수를 구할 수 있다.

primes :: Int -> [Int]
primes n = [x | x <- [2..n], prime x]

ghci> primes 40
[2,3,5,7,11,13,17,19,23,29,31,37]

키와 값의 순서쌍 리스트로 룩업 테이블(lookup table)을 표현할 때 가드를 이용해서 주어진 키에 해당하는 모든 값 리스트를 찾는 함수 find를 구현할 수 있다.

find :: Eq a => a -> [(a,b)] -> [b]
find k t = [v | (k',v) <- t, k == k']

ghci> find 'b' [('a',1),('b',2),('c',3),('b',4)]
[2,4]

함수 zip

라이브러리 함수 zip은 두 리스트의 원소를 순서대로 짝 지어서 새로운 리스트를 만든다. 이때 어느 한 쪽이 먼저 없어질 때까지 짝을 짓는다.

ghci> zip ['a','b','c'] [1,2,3,4]
[('a',1),('b',2),('c',3)]

리스트의 모든 원소에 대해서 바로 옆에 있는 원소끼리 짝을 지어주는 함수 pairs를 아래처럼 구현할 수 있다.

pairs :: [a] -> [(a,a)]
pairs xs = zip xs (tail xs)

ghci> pairs [1,2,3,4]
[(1,2),(2,3),(3,4)]

함수 pairs를 이용해서 리스트의 모든 원소가 정렬 되었는지 판단하는 함수 sorted를 구현할 수 있다.

sorted :: Ord a => [a] -> Bool
sorted xs = and [x <= y | (x,y) <- pairs xs]

ghci> sorted [1,2,3,4]
True

ghci> sorted [1,3,2,4]
False

prime과 마찬가지로 [1,3,2,4]의 정렬 여부를 판단할 때 함수 sorted가 모든 순서쌍을 끝까지 다 계산할 필요는 없다. (3,2)처럼 조건에 맞지 않는 순서쌍이 나오는대로 False가 리턴되기 때문이다.

positions :: Eq a => a -> [a] -> [Int]
positions x xs =
  [i | (x',i) <- zip xs [0..n], x == x']
  where n = length xs - 1

ghci> positions False [True,False,True,False]
[1,3]

문자열 컴프리헨션

하스켈에서 문자열은 문자 리스트이다. 예를 들어 "abc" :: String은 ['a','b','c'] :: [Char]와 같다. 그래서 리스트에 쓸 수 있는 함수는 문자열에도 쓸 수 있다.

ghci> "abcde" !! 2
'c'

ghci> take 3 "abcde"
"abc"

ghci> length "abcde"
5

ghci> zip "abc" [1,2,3,4]
[('a',1),('b',2),('c',3)]

같은 이유로 문자열에 사용하는 함수에 리스트 컴프리헨션을 이용할 수 있다. 문자열에서 소문자의 개수를 리턴하는 함수 lowers나 문자열에서 특정 문자의 개수를 세는 함수 count를 아래처럼 구현할 수 있다.

lowers :: String -> Int
lowers xs = length [x | x <- xs, isLower x]

count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x == x']

ghci> lowers "Haskell"
6

ghci> count 's' "Mississippi"
4

참고

• https://archive.org/details/programminginhas0000hutt