Цикл внутри монады ST - PullRequest
Новая
       44

Цикл внутри монады ST

2 голосов
/ 28 октября 2019

Я пытаюсь реализовать вставку сортировки в 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 должен иметь тип ST s i -> m (Either i (ST s ())), но из-заrunST метод сокрытия внутреннего состояния ST, fmap (mapLeft runST) . bubbleBackOnce ary имеет тип (forall s'. ST s' i) -> Either i (ST s i). Это мой первый раз, когда я использую ST, поэтому я не уверен, как решить эту проблему. Кроме того, это проект для домашних животных, поэтому я стараюсь не полагаться на существующие библиотеки, которые могли бы упростить некоторые вещи, например STMonadTrans.

...