알고리즘을 조금씩 공부해 보자는 취지를 같고 공부해 보려 하지 무엇 부터 해야 할지 막막하네요..
그러던중, 갑자기 알고리즘 책에 있는 문제들을 함수형 언어(Functional language)로 바꾸어 보면 어떨까 하는 생각이 들었습니다. 처음에는 정렬 알고리즘(sorting algorithm)중 빠른 정렬(Quick sort)을 구현하는데 함수형 언어가 너무나 아름다운 코드를 만들어 내어서 다른 정렬 알고리즘을 함수형 언어로 구현해 보는 건 어떨까 생각했는데 일이 커졌나 모르겠습니다. 뭐 아무튼, 일단 정렬에 대해서는 그렇게 할 것입니다...ㅋ

본론으로 들어가서
역시나 함수형언어는 알고리즘을 표현한는데 정말 좋은 것 같습니다.

다른 분들도 마찬가지 겠지만, 대부분의 한국 컴퓨터 공학과 학생들, 전산 관련된 사람들은 C를 비롯하, 명령형 언어(imperative language)를 먼저 배우게 됩니다. 그리고 자료구조, 알고리즘과 같은 전산학의 기반 지식을 배우게 되며 거기서 나오는 코드도 C, C++, java가 될 것입니다.

하지만 알고리즘을 공부하는데 명령형 언어가 효과적일까? 하는 의심이 들게 되었습니다. 이 의심은 순수히 저의 개인적인 경험에 의한 것이지만 다른 분들도 똑같이 않을까 생각 됩니다.

빠른 정렬(Quick sort)를 C로 구현을 하면 어떻게 해야 할까요?
기존의 책이나 인터넷을 통하지 않고 혼자서, 2 ~ 3분의 시간동안 코드를 짜보세요...


특히 컴퓨터 공학과 4학년이 되는 학생들이나(보통 2학년때 배우니까요..), 빠른 정렬 코드를 본지 오래된 사람이라면 쉽지 않을 거라 생각합니다. Pivot을 기준으로 Pivot보다 같거나 작은 것을 왼쪽에, 큰것을 오른쪽에 두고 각각을 재귀적으로(recursive)다시 빠른 정렬을 호출하면 되는데, 그 과정에 Pivot을 기준으로 왼쪽, 오른쪽으로 갈라내는 코드가 신경을 쓰이게 합니다. 이 신경쓰임은 사실 알고리즘을 구현하는데에 필요한 것이아니라, 언어의 특성을 따라서 알고리즘을 구현해야 하기 때문에 생기는 것입니다.

하지만 함수형 언어는 그렇지 않습니다.
정말 말 그대로 문제를 풀기위한 핵심만 기술하면 됩니다.

qsort :: Ord a => a -> a
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort bigger
where smaller = [a | a <- xs, a <= x]
bigger = [b| b <- xs, b > x]


위의 코드가 빠른정렬을 함수형 언어(하스켈)로 구현한 코드 입니다. 
정말 알고리즘에 필요한 것 외에는 아무것 도 없습니다.
첫 번째줄은 함수의 정의역과 공역을 나타내고 있습니다.
두 번째 둘은 재귀함수의 종료 조건(Terminal condition)을 나타내고 있습니다.
(다른 함수를 구현할때는 항등원, 역원이 올수도 있을 겁니다... 다 같은 말인가요?ㅎ)

마지막 세줄은 빠른 정렬의 핵심 알고리즘입니다. 문자의 집합 중 가장 앞에 있는 수를 기준으로 해서 기준보다 같거나 작은 것을 왼쪽에 두고, 기준보다 큰것을 오른쪽에 두어 재귀적으로 빠른 정렬을 구현한다... 교과서에 나오는 글을 그대로 표현한것과 같은 깔끔한 코드 입니다.

혹시나 제가 생각하는 것에 대해서 하실말씀이 많은 분들도 있을 것입니다만,
제가 함수형언어가 무조건적으로 좋다라는 것에는 저도 공감하지 않습니다. 단지, 알고리즘을 표현하는데에는 함수형 언어가 명령형 언어보다 좋은 것 같다입니다.




신고
by danguria 2010.02.27 15:36