Bubble sort in Haskell

함수형 프로그래밍을 알기 전에는 딱히 Imperative programming이란 말은 안썼던 것 같다. 의미도 잘 몰랐고…

“코딩도장”이란 사이트에서 가끔씩 문제를 풀어보는데, 아래의 문제가 나왔다.

“버블 소트에서 루프 카운트와 스왑 카운트를 구해라"

버블 소트만 해도 배열의 인접 요소를 스왑하는 알고리즘인데, 여기에 어떤 연산의 횟수를 따지라니… 이건 C 식구들에게는 매우 간단한 일이지만 Haskell 같은 순수 언어와는 어울리지 않는다.

어울리지 않는 것은 어울리지 않는 것이고, 방법은 알아두면 좋겠다 싶어서 Haskell로 Imperative programming!을 해보고 여기다 간단히 정리한다.


가장 쉬운 방법은 IO를 이용하는 것이다. IORef나 IOArray를 이용하면 C의 변수와 배열을 그대로 흉내낼 수 있다.

{-# LANGUAGE ScopedTypeVariables #-}
import Data.IORef
import Data.Array.MArray
import Data.Array.IO
import Control.Monad (forM_, when)
whileM_ p f = go where go = p >>= \x -> when x (f >> go)
bubbleSort as = do
arr :: IOArray Int a <- newListArray (1, length as) as
(l, h) <- getBounds arr
swapped <- newIORef True
newH <- newIORef h -- 스왑된 마지막 위치 기억, 다음에 여기까지만
whileM_ (readIORef swapped) $ do
writeIORef swapped False
h <- readIORef newH
forM_ [l .. h-1] $ \i -> do
a <- readArray arr i
b <- readArray arr (i+1)
when (a > b) $ do
writeIORef swapped True
writeArray arr i b
writeArray arr (i+1) a
writeIORef newH i
getElems arr
main :: IO ()
main = do
result <- bubbleSort [3, 1, 4, 1, 5, 9, 2, 6]
print result

bubbleSort 는 [a] -> IO [a]

여기에서 swap횟수를 반환하고 싶다면,

bubbleSort as = do
arr :: IOArray Int a <- newListArray (1, length as) as
(l, h) <- getBounds arr
swapped <- newIORef True
newH <- newIORef h
swapCount <- newIORef 0
whileM_ (readIORef swapped) $ do
writeIORef swapped False
h <- readIORef newH
forM_ [l .. h-1] $ \i -> do
a <- readArray arr i
b <- readArray arr (i+1)
when (a > b) $ do
writeIORef swapped True
writeArray arr i b
writeArray arr (i+1) a
writeIORef newH i
modifyIORef swapCount (+1)
readIORef swapCount

IORef를 C의 변수처럼 사용할 수 있다.

그런데, IO는 너무 무지막지한 녀석이어서 한번 IO를 사용하면 더이상 “순수"한 세계로 돌아올 수 없다.

그래서 ST를 이용할 수 있다. State thread를 의미하는데, 말하자면 순수한 세상 속에 미니 IO 세상을 넣는 것이다. IO는 IO인데, 외부와 완전히 단절된 세상이어서 순수한 세상에서는 그 속을 들여다보기 전에는 그것이 imperative인지 알 길이 없다. IO라는 지저분한 바깥 세상 속에 순수한 세상.. 그리고 그 속에 다시 ST라는 미니 IO 세상이 있는 것이다.

IOArray 대신 STArray, IORef 대신 STRef 를 사용할 수 있다. ST 세상에서 값을 꺼내려면 runST(혹은 runSTArray)를 이용한다.

bubbleSort as = elems $ runSTArray $ do
arr <- newListArray (1, length as) as
(l, h) <- getBounds arr
swapped <- newSTRef True
newH <- newSTRef h
whileM_ (readSTRef swapped) $ do
writeSTRef swapped False
h <- readSTRef newH
forM_ [l .. h-1] $ \i -> do
a <- readArray arr i
b <- readArray arr (i+1)
when (a > b) $ do
writeSTRef swapped True
writeArray arr i b
writeArray arr (i+1) a
writeSTRef newH i
return arr

이제 bubbleSort의 타입은? [a] -> [a]

IO를 떼어낸 bubbleSort는 순수함수다!