OCaml 실습, Quicksort

위키백과를 참고해서... 거의 그대로 짰습니다. OTL

let rec partition f l =
        match l with
        | [] -> ([],[])
        | hd::tl ->
                let ret = f hd in
                let (left, right) = (partition f tl) in
                if ret then (left @ [hd], right) else (left, right @ [hd])

let rec quicksort l =
        match l with
        | [] -> []
        | pivot::rest ->
                let is_less x = x < pivot in
                let (left, right) = partition is_less rest in
                quicksort left @ [pivot] @ quicksort right

let rec print_list f l =
        match l with
        | [] -> ()
        | hd::tl -> f hd; print_string " ";print_list f tl

let _ =
        let data = [3; 4; 1; 6; 10; 5; 2; 7] in
        let sorted = quicksort data in
        print_list print_int sorted

음, 일단 C나 자바를 건드리던 입장에서는 메모리 효율성으로만 보면 이것 참 걱정이 됩니다. 뭐, 일장일단이 있겠거니 하고 넘어가봅니다. 그런데 어째 파이썬 코드로도 비슷하게 짤 수 있겠다 싶습니다.

def partition(f, l):
        if len(l) == 0: return ([], [])
        hd = l[0]; tl = l[1:]
        (left, right) = partition(f, tl)
        if (f(hd)): return (left + [hd], right)
        else: return (left, right + [hd])

def quicksort(l):
        if len(l) == 0: return []
        pivot = l[0]; rest = l[1:]
        (left, right) = partition(lambda x: x < pivot, rest)
        return quicksort(left) + [pivot] + quicksort(right)

print quicksort([3, 4, 1, 6, 10, 5, 2, 7])

어때요. 아주 비슷한 느낌이죠? 파이썬에서도 함수가 객체로 취급되어 인자로 쉽게 넘길 수 있고, 형식을 명시하지 않기 때문에 프로그램 구조에서 아주 비슷한 냄새가 폴폴 풍깁니다.

반면, 파이썬은 아주 말랑말랑하지만 OCaml은 딱딱하다 못해 이빨이 부러질 정도라는 차이가 있습니다. 기본적으로 형식 추론과 동적 타이핑의 문제기도 합니다. 그에 더해, OCaml은 거의 대부분의 자료형들이 Immutable한 느낌입니다. 반면, 파이썬은 기본적으로 모든 객체들이 Mutable한 편입니다. 런타임에도 객체에 새로운 속성과 메서드를 집어넣을 수 있으니까요(경악). 어찌 보면 각자 죽이 맞는 조합이지만, 서로 성격이 완전히 다릅니다.

여하튼 이런 특성들에 대해서 이야기를 나눠볼 분이... 있으려나요! ^^;