개미 수열의 하스켈 구현

2008/12/04 | No comments

개미 수열이란게 있습니다. 베르나르 베르베르의 소설 “개미” 에 나와서 유명해진 수열인데, 대략 아래와 같은 형태입니다.

1
11
12
1121
122111
112213
12221131
…

처음 보는 분들을 위해 간단히 설명하자면, 일단 수열의 처음은 “1” 로 시작합니다. 그리고 그 다음 원소부터는 이전 원소의 숫자들을 읽어서 만들어냅니다.

우선 첫 원소 “1” 은 1이 1개 있기 때문에 두번째 원소는 “11” (1이 1개) 가 됩니다.

그 다음 원소는 이전 원소가 “11” 이므로 “12” (1이 2개), 또 그 다음 원소는 “1121” (1이 1개, 2가 1개) 가 됩니다.

이와 같은 규칙으로 생성되는 수열인데, 문제가 간단해서 Haskell 이라는 함수형 언어(functional programming language)로 한번 작성해보았습니다.

module AntSeq
    where

ant_seq [] = []
ant_seq l@(x:xs) = let (xs1, xs2) = span ((==) x) l
                   in x : (length xs1) : ant_seq xs2

gen_seq n = take n $ iterate (ant_seq) [1]

--pretty print
pprint n = mapM_ print $ gen_seq n

위 하스켈 코드를 ant_seq.hs 파일로 저장한 다음 하스켈 인터프리터에서

:load ant_seq.hs

한 후 pprint 함수를 실행시키면 아래와 같이 출력됩니다.

*AntSeq> pprint 12
[1]
[1,1]
[1,2]
[1,1,2,1]
[1,2,2,1,1,1]
[1,1,2,2,1,3]
[1,2,2,2,1,1,3,1]
[1,1,2,3,1,2,3,1,1,1]
[1,2,2,1,3,1,1,1,2,1,3,1,1,3]
[1,1,2,2,1,1,3,1,1,3,2,1,1,1,3,1,1,2,3,1]
[1,2,2,2,1,2,3,1,1,2,3,1,2,1,1,3,3,1,1,2,2,1,3,1,1,1]
[1,1,2,3,1,1,2,1,3,1,1,2,2,1,3,1,1,1,2,1,1,2,3,2,1,2,2,2,1,1,3,1,1,3]

함수형 언어는 특정 타입의 문제들을 아주 깔끔하고 간단하게 구현하는 것이 가능합니다. 그러나 그런 몇가지 예제들을 가지고 함수형 언어가 마치 모든 문제의 가장 완전하고 빠른 해결책인 것처럼 오도하는 것은 분명 경계해야 할 것입니다.

이 예제는 함수형 언어의 특징을 효과적으로 보여주는 그런 전형적인 예제들과는 거리가 멀지만, 생각보다 코드가 간단하게 나와서 포스팅 해봤습니다.

간단한 문제이므로 각자 선호하는 언어로 구현해 보고 비교해보는 것도 재미있을 것 같습니다.