헤스켈 셀렉션 소트 구현.. 헐.

haskell 잠깐 구경하는 중인데 이걸로 selection sort 를 짜보려다 좌절을 먹고 소감이나 적어둔다.

for i ← 0 to n-2 do
    min ← i
    for j ← (i + 1) to n-1 do
        if A[j] < A[min]
            min ← j
    swap A[i] and A[min]

처음엔 selection sort 의 정의 그대로 2중 루프 돌면서 작은 값 찾아서 자리바꾸는 식으로 구현을 해보려고 했는데 이렇게 접근하니 아주 제한적인 부분만 알고있는 내 haskell 능력으로는 구현이 불가능하더라.

루프야 대강 재귀돌리면 되는데 문제는 swap.. haskell 의 리스트가 싱글링크드리스트 인것 같은데 이걸 어떻게 효율적으로 스왑을 하나.. 처음엔 당연히 스왑함수가 지원될줄 알았는데 안보이네.. 그리고 이걸 짜보려고 해도 이놈의 리스트가 불변값이라 어쩔수 없이 여러번의 복사? 가 일어날듯 해보였다.

물론 리스트를 조각내서 짜깁기 하는식으로 짜면야 간단하긴 한데... 아무래도 남들은 이런식으로 쓰지 않을거란 생각이 들었다.

그래서 대강 찾아보니 IO array 라던지 ST array 라던지 하는 수정가능한 자료구조가 있다는건 알게됐는데 문제는 이놈들이 모나드... 아직 모나드 공부는 안했지만 모나드와 다른 함수들이 자연스럽게 섞이지 않는 문제점을 겪었기에 ( 아직 공부중이라 잘 몰라서 그럴수도 있지. 하지만 모나드 라는게 사이드 이펙트를 막고자 나온거라면 모나드 함수가 비 모나드 함수안에서 투명하게 불리는것은 불가능하겠지? )..

... 모나드에 겁을 먹고 바로 구글링을 해봤다.

결국 http://www.cs.bris.ac.uk/Teaching/Resources/COMS12100/2003-4/lectures/notes.html 에서 셀렉션 소트 구현을 찾았는데

mport List

selectSort :: Ord a => [a] -> [a]
selectSort [] = []
selectSort ns =
   m : selectSort (remove m ns)
   where m = minimum ns

insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (n:ns) =
   insert n (insertSort ns)
이렇더라.. 음..
헐... 놀랍다.
함수형 언어와 절차형 언어의 접근이 다르다는걸 머리론 알고 있었지만 그걸 느끼긴 처음이네.
그리고 이미 몇년간 C/C++ 식 코딩을 해온 나한테 저런건 머리를 쥐어짜도 안나올거란걸 느꼈다.

좀더 공부를 해볼까? 그냥 접을까?


PS 그런데 저 잘난 구현도 리스트의 사본을 계속해서 만드는데 기분이 편치 않네.
성능 생각하면 모나드쪽의 어래이를 써야 할것 같은데 정말 헤스켈로 프로젝트 뛰는
애들이 어떤식으로 코딩하는지 궁금하네.