2

我正在尝试在 Haskell 上实现插入排序Data.Array.ST，并使用一元比较函数。即，sortByM :: (Monad m, Ix i, Enum i, Eq i) => (e -> e -> Ordering) -> STArray s i e -> m (ST s ())。这是我的代码，用于上下文：

import Data.Ord
import Data.Foldable
import Data.Array.ST
import Control.Monad.ST

sortByM :: (Monad m, Ix i, Enum i, Eq i) 
        => (e -> e -> m Ordering) 
        -> STArray s i e -> m (ST s ())
sortByM cmp xs = sequence_ <$> traverse (bubbleBack xs) [start..end]
  where 
        (start, end) = runST $ getBounds xs
        bubbleBack :: (Monad m, Ix i, Enum i, Eq i) 
                   => STArray s i e -> i -> m (ST s ())
        bubbleBack ary = loopM $ fmap (mapLeft runST) . bubbleBackOnce ary
        bubbleBackOnce :: (Monad m, Ix i, Enum i, Eq i) 
                        => STArray s i e 
                        -> i -> m (Either (ST s i) (ST s ()))
        bubbleBackOnce ary bubble = 
           if bubble == start
           then return $ Right $ return ()
           else do
                  let elem = runST $ readArray ary bubble
                  let prev = runST $ readArray ary (pred bubble)
                  ordering <- cmp elem prev
                  return $ if ordering == LT
                           then Left $ do
                                         writeArray ary bubble prev
                                         writeArray ary (pred bubble) elem
                                         return $ pred bubble
                           else Right $ return ()
-- ...
mapLeft :: (a -> r) -> Either a b -> Either r b
mapLeft f (Left x)  = Left (f x)
mapLeft _ (Right x) = Right x

据我了解，我遇到的问题是loopM' 的第一个参数应该有 type ST s i -> m (Either i (ST s ()))，但由于runST' 隐藏ST内部状态的方法，fmap (mapLeft runST) . bubbleBackOnce ary有 type (forall s'. ST s' i) -> Either i (ST s i)。这是我第一次使用 ST，所以我不知道如何解决这个问题。此外，这是一个宠物项目，所以我试图避免依赖现有的可以简化事情的库，例如STMonadTrans。

4

0 回答 0