하스켈 무한 리스트

하스켈은 유한한 리스트뿐만 아니라 무한히 긴 리스트를 정의할 수 있습니다. 예를 들어,[m..]은 m에서 시작하는 모든 정수의 리스트가 됩니다.

> [1..]
[1,2,3,4,5,6,7,8Interrupted.
>

ghci[1..]을 입력하면 이 리스트를 화면에 출력하는데, 무한히 긴 리스트이므로 끝이 나지 않고 계속해서 숫자를 출력하는 것을 보실 수 있습니다. Ctrl+C 키를 눌러서 종료하면 Interrupted 메시지와 함께 출력이 종료됩니다.

리스트 기초에서 살펴본 take 함수를 이용하면 무한히 긴 리스트에서 일부 원소만 뽑아낼 수 있습니다.

> take 10 [1..]
[1,2,3,4,5,6,7,8,9,10]

같은 리스트를 [1..]과 같은 표기법을 이용하지 않고 재귀적으로 정의할 수도 있습니다. 이렇게 정의한 ints 리스트에서 take 함수로 10개 처음 10개 원소를 꺼내보면 [1..]과 마찬가지로 1부터 10까지 정수의 리스트를 리턴하는 것을 볼 수 있습니다.

> let ints = 1 : map (+1) ints
> take 10 ints
[1,2,3,4,5,6,7,8,9,10]

ints가 어떻게 동작하는지를 이해하기 위해 원소를 차례대로 하나씩 꺼내보겠습니다.ints는 머리 1과 꼬리 map (+1) ints로 구성된 리스트이기 때문에 ints의 첫 번째 원소는 1입니다. 두 번째 원소는 map (+1) ints의 머리입니다. map (+1)은 주어진 리스트의 모든 원소에 1을 더해주는데, 여기서는 다시 ints를 인자로 넘겼습니다. 이 ints의 첫 번째 인자는 1이였으므로 map (+1) ints의 첫 번째 원소는 11을 더한 2가 됩니다. 따라서 전체 ints의 두 번째 인자도 2가 됩니다. 같은 방법으로 세 번째 원소를 꺼내면 3이 되는 것을 확인할 수 있습니다.

이런 무한 리스트도 유한한 리스트와 마찬가지로 map이나 filter 같은 함수들을 사용해 원소를 원하는 대로 바꿀 수 있습니다. 아래 예제에서 evensints 리스트의 각 원소에2를 곱한 짝수의 리스트입니다. take 함수로 10개를 뽑아보면 2부터 20까지 짝수 10개가 리턴되는 것을 볼 수 있습니다.

> let ints = 1 : map (+1) ints
> let evens = map (*2) ints
> take 10 evens
[2,4,6,8,10,12,14,16,18,20]

조금 더 간단한 예로 1이 무한히 반복되는 리스트를 정의해 볼 수도 있습니다.

> let ones = 1 : ones
take 10 ones
[1,1,1,1,1,1,1,1,1,1]

ones의 머리는 1이고 꼬리는 다시 ones입니다. 따라서 ones의 두 번째 원소는 ones의 머리이므로 1이고, 세 번째, 네 번째 원소도 모두 1이 되는 것을 알 수 있습니다.

하스켈은 무한 리스트를 정의하는 경우가 많으므로 Prelude 모듈에서는 편의를 위해iterate를 함수를 제공합니다. iterate 함수는 함수 f를 인자 x에 0번, 1번, 2번, … 반복해서 호출하여 리스트를 만들어줍니다.

iterate f x == [x, f x, f (f x), ...]

iterate 함수를 이용해서 ints를 정의할 수도 있습니다.

> let ints = iterate (+1) 1

iterate (+1) 1[1, (+1) 1, (+1) $ (+1) 1, (+1) $ (+1) $ (+1) 1, ...]와 동일하고,(+1) $ (+1) 1은, (+2) 1과 같으므로 위 리스트는 [1..]과 같다는 사실을 쉽게 확인할 수 있습니다.

iterate 함수로 ones도 정의할 수 있습니다.

> let ones = iterate id 1

여기서는 iterate 함수의 인자로 id를 넘겼습니다. idSKI 콤비네이터에서 살펴보았던 항등 함수(identity function)로 인자를 받아 그대로 리턴합니다. iterate id 1[1, id 1, id $ id 1, id $ id $ id 1, ..]이므로 모든 원소가 1이 되는 것을 확인할 수 있습니다.

이런 경우에는 repeat 함수를 이용하면 더 간단합니다. repeat 함수는 주어진 인자 x를 무한히 반복합니다.

> let ones = repeat 1

이런 무한 리스트는 zip 함수와 같이 사용하는 경우가 많습니다. zip 함수는 리스트 두 개를 인자로 받아 각 리스트이 원소를 하나씩 뽑아 묶은 튜플의 리스트를 리턴합니다. 간단한 예를 보면,

> zip [1,2,3,4,5] ['a', 'b', 'c', 'd', 'e']
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]

두 리스트 중 한 쪽이 짧으면 먼저 끝나는 쪽을 기준으로 끝이 납니다.

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

zip 함수를 이용하여 리스트 각 원소의 인덱스를 매기고 싶은데, 리스트이 길이를 미리 알 수 없다면 어떻게 해야 할까요? 이런 경우 [1..]와 같이 무한히 긴 인덱스의 리스트를 넘기면 됩니다.

> let ls = ['a', 'b', 'c', 'd', 'e']
> zip [1..] ls
[(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]

One thought on “하스켈 무한 리스트

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s