하스켈로 알고리즘을 구현하는 것이 좀더 큰 목적이지만, 그렇다고 알고리즘 구현에 뛰어난 것이 아니기 때문에 복습도 해볼겸해서 정렬알고리즘을 하스켈로 구현하고 각각의 특징을 정리 해보려고 합니다. 
그 1탄으로 Insertion sort, Selection sort, Merge sort, Quick sort입니다.
오늘은 어려운 코드가 아니므로 알고리즘 구현에 대한 자세한 설명은 생략하는 것이 좋을 것 같습니다.
일단 코드 부터 보겠습니다. 기존에 C와 다른 코드 이므로 좀더 신중하게 보세요.. 
하스켈을 모르셔도 읽는데는 무리가 없을 것이라고 생각합니다. (필요한부분은 설명을 하도록 하겠습니다.)

-- this function is inserttion sort
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
| x < y  = x : y : ys
| otherwise = y : insert x ys 
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)

위의 코드는 Insertion sort입니다. 보통 책에는 Iterative하게 구현했지만 함수형 언어의 특징을 살려 recursive함수로 구현했습니다. (참고로, 저도 아직 배우는 중이라서 비슷하게는 구현했지만 부족한 부분은 인터넷에 떠도는 멜버른 대학의 코드를 가져 왔습니다.)

-- this function is selection sort
myMin :: Ord a => [a] -> a
myMin [] = undefined 
myMin [x] = x 
myMin (x:xs) 
| x <= myMin(xs) = x
| otherwise = myMin(xs)
delete :: Eq a => a -> [a] -> [a]
delete x [] = []
delete x (y:ys)
| x == y = ys
| otherwise = y : (delete x ys)    
ssort :: Ord a => [a] -> [a]
ssort [] = []
ssort xs = [x] ++ ssort (delete x xs) 
where x = myMin (xs)

이번 코드는 Selection sort입니다. 개인적으로 이 코드를 구현하는게 좀더 쉬었네요...

-- this function is merge sort 
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
| x <= y = x : (merge xs (y:ys))
| otherwise = y : (merge (x:xs) ys)
msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort top) (msort bottom)
where (top, bottom) = splitAt (length xs `div` 2) xs

이번 코드는 Merge sort입니다. 조심하셔야 하는 것은 종료 조건을 정확하게 기준해야 한다는 점입니다. 정렬 알고리즘을 재귀함수로 구현 하기 때문에 종료 조건이 특히 중요 합니다. 다른 언어보다 알고리즘을 표현하기 쉽기 때문에 이런 부분만 신경쓴다면 알고리즘 외의 부분에서는 오류 날일이 거의 없을 듯 합니다.

-- this function is quick sort
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]  

개인적으로 하스켈을 공부한지 한달 정도 되었는데, 이 코드가 가장 좋아 하는 코드 입니다. 너무너무나 Clear하죠^^(저희 학교에 어떤 교수님께서 잘 쓰시는 말을 인용했습니다.)
신고
by danguria 2010.02.27 16:05
알고리즘을 조금씩 공부해 보자는 취지를 같고 공부해 보려 하지 무엇 부터 해야 할지 막막하네요..
그러던중, 갑자기 알고리즘 책에 있는 문제들을 함수형 언어(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
| 1 |