함수형 언어로 구현한 퀵정렬

언어의 한계가 사고의 한계다.
- 비트겐슈타인

아주 오래 전에, 그러니까 C/C++, Java 외 다른 언어는 공부할 필요가 없다고 생각했던 때에, 잡지에서 다음과 같은 코드를 본 적이 있다.

qsort [] = []
qsort (p:xs) = qsort [y | y <- xs, y < p] ++ [p] ++ qsort [y | y <- xs, y >= p]

Haskell로 작성한 퀵정렬 코드였다. C나 Java로 구현했다면 스무 줄 정도의 코드가 필요할텐데, Haskell로는 단 두 줄로 끝냈다는 사실이 놀라웠다. 그러나 저 암호 같은 코드를 해석해 볼 엄두는 내지 못했다. '흥미롭긴 하지만 많이 사용되는 언어도 아니잖아. 공부해봤자 별로 쓸 데도 없을 거야.'하며 자위했을 뿐이다.

그 후로도 Haskell을 공부한 적은 없지만, 지금은 위 코드를 대충 이해할 수 있게 되었다. 최근에 다른 함수형 프로그래밍 언어를 공부했기 때문일 것이다. []는 빈 리스트일테고, ++는 리스트를 연결(concatenate)하는 연산자일 것이다. [y | y <- xs, y < p] 수학 시간에 집합에서 배웠던 표기법과 비슷하다. xs의 원소 중 p보다 작은 원소만 모아 놓은 리스트일 것이다. p:xs는 리스트의 첫 번째 원소를 p, 나머지를 xs로 참조하는 것일 게다. Scala의 패턴 매칭이나 Clojure의 destructuring과 비슷한 것으로 볼 수 있을 듯 하다.

즉, 리스트의 첫 번째 원소(p)를 기준으로 값이 작은 녀석들은 왼쪽으로, 값이 큰 녀석들은 오른쪽으로 나누어 배치한다. 그리고 왼쪽, 오른쪽에 배치한 리스트를 다시 재귀적으로 qsort 함수를 호출한다. 이해하고 나면, 코드가 퀵정렬 알고리즘을 그대로 표현하고 있는게 보인다.

눈으로 보고 이해하는 것만으로는 충분하지 않다. 직접 짜보고 실행해봐야 제대로 알 수 있다. 그래서 내가 좋아하는 Clojure로 직접 구현해보았다.

(defn qsort [[p & xs]]
  (if (nil? p)
    '()
    (let [l (filter #(< % p) xs), r (filter #(>= % p) xs)]
      (lazy-cat (qsort l) (list p) (qsort r)))))

Haskell 코드보다 조금 길지만 기본 로직은 같다.

정렬할 리스트에 같은 값이 여러 번 나오는 경우도 고려한다면 compare 함수로 group-by하는 편이 좀더 효율적일 것 같다.

(defn qsort [[p :as coll]]
  (if (nil? p)
    '()
    (let [{l -1 m 0 r 1} (group-by #(compare % p) coll)]
      (lazy-cat (qsort l) m (qsort r)))))

리스트의 첫 번째 요소를 기준으로 다른 값을 왼쪽, 오른쪽으로 보내는 대신, 여기서는 리스트의 첫 번째 요소(p)와 compare 함수로 값을 비교한다. p보다 작은 값들은 -1 그룹(l)으로, 같은 값들은 0 그룹(m)으로, 큰 값들은 1 그룹(r)으로 묶일 것이다.

Haskell로 작성된 퀵정렬 코드를 처음 봤던 그때, Haskell을, 함수형 프로그래밍을 공부했더라면 어땠을까? 회사 동료가 Haskell을 공부하자고 했었지만 '그런 것 공부해서 어디에 쓰겠냐?'며 거절했던 생각이 난다. 다른 고참이 Python을 공부하자고 했을 때도 응하지 않았다. 나는 Basic, Pascal, Fortran, C/C++, Cobol, Java 등 여러 언어를 공부했었고, 언어는 모두 거기서 거기라 기본적인 문법과 라이브러리 사용법만 익히면 어떤 언어로든 금방 프로그램을 작성할 수 있다는 자만심에 빠져 있었다. 생각해보니 그때까지 내가 알던 언어는 모두 같은 패러다임의 언어였다. 그게 내 한계였다.

후회된다. 그때 함수형 언어에 관심을 가지고 공부를 시작했더라면 훨씬 넓은 세상을 봤을 테고, 훨씬 나은 프로그래머가 되어 있을지도 모르겠다는 생각이 든다. 동료들에게 함수형 프로그래밍을 공부하자고 꼬셔봤지만 넘어온 사람은 거의 없다. 그 친구들이 나와 같은 후회를 하지 않기 바란다.

참고

• Sorting algorithms/Quicksort 다양한 언어로 구현한 퀵정렬 코드를 볼 수 있다. 함수형 언어로 작성된 코드는 여기서 설명한 코드와 모양이 거의 비슷하다.
• Quicksort in Haskell Haskell과 C로 구현한 퀵정렬 코드를 비교하며 함수형 언어의 장점을 설명한다.