알고리즘을 조금씩 공부해 보자는 취지를 같고 공부해 보려 하지 무엇 부터 해야 할지 막막하네요..
그러던중, 갑자기 알고리즘 책에 있는 문제들을 함수형 언어(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


때마침 좋은 한국어로 번역된이 나와서 공부해보고 있습니다.

imperative language(이하 명령형 언어)만 공부하다가 functional language(이하 함수형 언어)를 공부하니까 알고리즘 구현하는데에 굉장히 좋은 언어라는 생각이 들었습니다. 이 생각이 맞는지 모르겠지만 표현 법이 고등학교에어 배운 수학적인 표현을 사용하고 생각한 알고리즘을 그대로 표현 하기만 하면 되는 것입니다. 즉, 명령형언어에서는 변수 선언 하고 동적할당 등등 시스템에 대한 이해를 요하고 그것을 코드에 적어 주어야 하지만 함수형 언어는 말하고자 하는(구현하고자 하는) 것만 표현 하면 되므로 굉장히 마음에 들었습니다. 물론 이 언어가 시스템 프로그래밍 하는데에는 부적격인 것 같아서 나름 장단점이 있는 것 같지만 필요에 따라서 유효 적절하게 쓰면 굉장히 좋을 것 같네요..

지금 1/3 가량 읽고 있는데 친구들이랑 스터디를 해서 작은 프로젝트 하나 해 보고 싶네요..

신고
by danguria 2010.02.04 21:11
| 1 |