Tardis monad kullanılarak herhangi bir taşınabilir konteynerin üzerinde bir kabarcık sıralaması uygulamaya çalışıyorum.Kabarcık sıralamasındaki sonsuz döngü Haskell'de geçiş yapılabilir
{-# LANGUAGE TupleSections #-}
module Main where
import Control.DeepSeq
import Control.Monad.Tardis
import Data.Bifunctor
import Data.Traversable
import Data.Tuple
import Debug.Trace
newtype Finished = Finished { isFinished :: Bool }
instance Monoid Finished where
mempty = Finished False
mappend (Finished a) (Finished b) = Finished (a || b)
-- | A single iteration of bubble sort over a list.
-- If the list is unmodified, return 'Finished' 'True', else 'False'
bubble :: Ord a => [a] -> (Finished, [a])
bubble (x:y:xs)
| x <= y = bimap id (x:) (bubble (y:xs))
| x > y = bimap (const $ Finished False) (y:) (bubble (x:xs))
bubble as = (Finished True, as)
-- | A single iteration of bubble sort over a 'Traversable'.
-- If the list is unmodified, return 'Finished' 'True', else 'Finished' 'False'
bubbleTraversable :: (Traversable t, Ord a, NFData a, Show a) => t a -> (Finished, t a)
bubbleTraversable t = extract $ flip runTardis (initFuture, initPast) $ forM t $ \here -> do
sendPast (Just here)
(mp, finished) <- getPast
-- For the first element use the first element,
-- else the biggest of the preceding.
let this = case mp of { Nothing -> here; Just a -> a }
mf <- force <$> getFuture -- Tardis uses lazy pattern matching,
-- so force has no effect here, I guess.
traceM "1"
traceShowM mf -- Here the program enters an infinite loop.
traceM "2"
case mf of
Nothing -> do
-- If this is the last element, there is nothing to do.
return this
Just next -> do
if this <= next
-- Store the smaller element here
-- and give the bigger into the future.
then do
sendFuture (Just next, finished)
return this
else do
sendFuture (Just this, Finished False)
return next
where
extract :: (Traversable t) => (t a, (Maybe a, (Maybe a, Finished))) -> (Finished, t a)
extract = swap . (snd . snd <$>)
initPast = (Nothing, Finished True)
initFuture = Nothing
-- | Sort a list using bubble sort.
sort :: Ord a => [a] -> [a]
sort = snd . head . dropWhile (not . isFinished . fst) . iterate (bubble =<<) . (Finished False,)
-- | Sort a 'Traversable' using bubble sort.
sortTraversable :: (Traversable t, Ord a, NFData a, Show a) => t a -> t a
sortTraversable = snd . head . dropWhile (not . isFinished . fst) . iterate (bubbleTraversable =<<) . (Finished False,)
main :: IO()
main = do
print $ sort ([1,4,2,5,2,5,7,3,2] :: [Int]) -- works like a charm
print $ sortTraversable ([1,4,2,5,2,5,7,3,2] :: [Int]) -- breaks
bubble
ve bubbleTraversable
arasındaki temel fark Finished
bayrak işlenmesidir: bubble
yılında farz ederiz en sağdaki eleman zaten sıralanır ve ona solundaki unsurları' hizmet etmeyen, bayrağını değiştirmek t; bubbleTraversable
numaralı telefondan bunu başka bir şekilde yapıyoruz.
<<loop>>
ile kanıtlandığı gibi program yavaş referanslarda sonsuz bir döngüye girer
mf
bubbleTraversable
değerlendirmek için çalışırken.
sorun forM
monadic zincirleme yeri (özellikle forM
listeler için flip traverse
olan) gerçekleşmeden önce, arka arkaya unsurları değerlendirmek çalıştığı, muhtemelen. Bu uygulamayı kurtarmak için herhangi bir yolu var mı? Her şeyden
Bu, şu anda içine bakmak için zamanım olmadığı mükemmel bir sorudur. Bu tartışmayı Traversables'i sıralamak istiyorum: https://www.reddit.com/r/haskell/comments/63a4ea/fast_total_sorting_of_arbitrary_traversable/ Zaten farkında değildiysen, belki ondan bazı fikirler alabilirsin. . – Carl