[sorting] 미니멀리스트, 예인 Haskell 퀵소트가 “진정한”퀵소트가 아닌 이유는 무엇입니까?

다음은 “진정한”quicksort C 코드를 Haskell로 음역 한 것입니다. 자신을 보호하십시오.

import Control.Monad
import Data.Array.IO
import Data.IORef

qsort :: IOUArray Int Int -> Int -> Int -> IO ()
qsort a lo hi = do
  (h,l,p,t) <- liftM4 (,,,) z z z z

  when (lo < hi) $ do
    l .= lo
    h .= hi
    p .=. (a!hi)

    doWhile (get l .< get h) $ do
      while ((get l .< get h) .&& ((a.!l) .<= get p)) $ do
        modifyIORef l succ
      while ((get h .> get l) .&& ((a.!h) .>= get p)) $ do
        modifyIORef h pred
      b <- get l .< get h
      when b $ do
        t .=. (a.!l)
        lVal <- get l
        hVal <- get h
        writeArray a lVal =<< a!hVal
        writeArray a hVal =<< get t

    lVal <- get l
    writeArray a hi =<< a!lVal
    writeArray a lVal =<< get p

    hi' <- fmap pred (get l)
    qsort a lo hi'
    lo' <- fmap succ (get l)
    qsort a lo' hi

재미 있지 않았나요? 나는 실제로 let처음과 where함수의 끝 에서이 큰 부분을 잘라내어 모든 도우미를 정의하여 앞의 코드를 다소 예쁘게 만듭니다.

  let z :: IO (IORef Int)
      z = newIORef 0
      (.=) = writeIORef
      ref .=. action = do v <- action; ref .= v
      (!) = readArray
      (.!) a ref = readArray a =<< get ref
      get = readIORef
      (.<) = liftM2 (<)
      (.>) = liftM2 (>)
      (.<=) = liftM2 (<=)
      (.>=) = liftM2 (>=)
      (.&&) = liftM2 (&&)
  -- ...
  where doWhile cond foo = do
          foo
          b <- cond
          when b $ doWhile cond foo
        while cond foo = do
          b <- cond
          when b $ foo >> while cond foo

그리고 여기에서 그것이 작동하는지 확인하는 멍청한 테스트입니다.

main = do
    a <- (newListArray (0,9) [10,9..1]) :: IO (IOUArray Int Int)
    printArr a
    putStrLn "Sorting..."
    qsort a 0 9
    putStrLn "Sorted."
    printArr a
  where printArr a = mapM_ (\x -> print =<< readArray a x) [0..9]

저는 Haskell에서 명령형 코드를 자주 작성하지 않기 때문에이 코드를 정리할 수있는 많은 방법이 있다고 확신합니다.

그래서 뭐?

위의 코드가 매우 길다는 것을 알 수 있습니다. 핵심은 C 코드만큼 길지만, 각 줄은 종종 좀 더 장황합니다. 이것은 C가 당연한 것으로 생각할 수있는 많은 불쾌한 일을 비밀리에 수행하기 때문입니다. 예 : a[l] = a[h];. 이것은 변경 가능한 변수 l및 h에 액세스 a한 다음 변경 가능한 배열에 액세스 한 다음 변경 가능한 배열을 변경합니다 a. 이런 돌연변이, 배트맨! Haskell에서 변경 및 변경 가능한 변수에 액세스하는 것은 명시 적입니다. “가짜”qsort는 여러 가지 이유로 매력적이지만 그중 가장 중요한 점은 돌연변이를 사용하지 않는다는 것입니다. 이 자체적으로 부과 된 제한은 한눈에 이해하기 훨씬 쉽게 만듭니다.

답변

main = putStrLn (show (quicksort [8, 6, 7, 5, 3, 0, 9]))