打破 forM_（使用可变向量插入排序）

Question

我正在使用可变向量在 Haskell 中编写插入排序。我不知道如何打破 forM_ 循环。我已经评论了我需要这样做的地方。

mvInsertionSort :: Ord a => Mv.IOVector a -> IO (Mv.IOVector a)
mvInsertionSort mv = do
    forM_ [1 .. Mv.length mv - 1] $ \x -> do
        pivot <- Mv.read mv x
        forM_ [x-1 , x-2 .. 0] $ \y -> do
            currElem <- Mv.read mv y
            if pivot < currElem then Mv.write mv y pivot >> Mv.write mv (y+1) currElem
                else Mv.write mv (y+1) pivot -- Exit out of the second forM_ loop here
    return mv

Answer 1

好吧，你总是可以使用延续 monad 来提供额外的 return 点：

import Control.Monad
import Control.Monad.Trans.Cont
import Data.Vector.Mutable as Mv

    mvInsertionSort :: Ord a => Mv.IOVector a -> IO (Mv.IOVector a)
    mvInsertionSort mv = do
     () <- evalContT $ callCC $ \exit ->
             forM_ [1 .. Mv.length mv - 1] $ \x ->
              do pivot <- Mv.read mv x
                 forM_ [x-1 , x-2 .. 0] $ \y ->
                  do currElem <- Mv.read mv y
                     if pivot < currElem
                         then do Mv.write mv y pivot
                                 Mv.write mv (y+1) currElem
                         else do Mv.write mv (y+1) pivot
                                 exit ()
     return mv

但我认为大多数人只是编写自定义递归定义。

打破 forM_（使用可变向量插入排序）

Breaking out of a forM_ (insertion Sort with mutable vectors)

haskell

insertion-sort