ST monad下可变向量分块修改的代码错误排查求助

核心错误分析 #

• whileM_ 参数错误：whileM_的正确签名是Monad m => m Bool -> m () -> m ()，你之前的调用传参方式完全不符合要求，它只接受两个monadic动作：循环条件和循环体。
• 可变/不可变向量混淆：V.Vector（不可变）和MV.MVector（可变）是不同类型，V.minimum只能作用于不可变向量，不能直接用于可变向量；所有可变向量的读写操作必须在ST monad内部执行。
• applyChain 逻辑错误：嵌套runST会破坏ST状态的连续性，且函数名拼写错误（applyCHain），索引操作vM MV.! i是ST动作，不能直接作为MV.write的参数。
• 类型签名不匹配：辅助函数的类型没有和ST monad以及向量类型对应，比如testMin的参数应该是可变向量而非不可变向量。

修正后的完整代码 #

import qualified Data.Vector as V
import qualified Data.Vector.Unboxed.Mutable as MV
import Control.Monad.Loops (whileM_)
import Data.Maybe (fromJust, elemIndex, isJust)

buildChain :: Int -> Int -> [(Int, Int)]
buildChain n limit = bCH n limit []
    where
        bCH n limit ls
            | n > limit = zip (replicate (length ls) 1) ls
            | elem n ls = let isChain = takeWhile (/=n) ls ++ take 1 (dropWhile (/=n) ls)
                              notChain = drop (length isChain) ls
                              chainLen = fromJust (elemIndex n ls) + 1
                          in zip (replicate (length notChain) 1) notChain ++ zip (replicate (length isChain) chainLen) isChain
            | otherwise = bCH (sumFactors n) limit (n:ls)
        sumFactors n = sum $ 1 : concat [[x, div n x] | x <- [2..floor $ sqrt $ fromIntegral n], rem n x == 0]

mapChain :: Int -> V.Vector Int
mapChain limit = runST $ do
    vM <- MV.replicate (limit + 1) 0
    MV.write vM 0 1
    -- 循环直到没有未处理的0值索引
    whileM_ (findZero vM >>= return . isJust) $ do
        Just targetIdx <- findZero vM
        let chainResult = buildChain targetIdx limit
        applyChain vM chainResult
    V.freeze vM
    where
        -- 查找第一个值为0的索引，返回Maybe Int
        findZero :: MV.MVector s Int -> ST s (Maybe Int)
        findZero v = go 0
            where
                go i
                    | i > limit = return Nothing
                    | otherwise = do
                        val <- MV.read v i
                        if val == 0 then return (Just i) else go (i + 1)
        -- 将buildChain的结果写入可变向量，仅修改未设置的位置
        applyChain :: MV.MVector s Int -> [(Int, Int)] -> ST s ()
        applyChain _ [] = return ()
        applyChain v ((len, num):rest) = do
            currentVal <- MV.read v num
            if currentVal == 0 then MV.write v num len else return ()
            applyChain v rest

关键修正说明 #

1. whileM_ 正确用法：

   • 循环条件通过findZero检查是否存在未处理的0值索引，返回ST s Bool类型的结果。
   • 循环体中获取第一个0索引，调用buildChain生成结果，再通过applyChain写入向量。

2. 可变向量操作修正：

   • 用findZero遍历可变向量寻找第一个0索引，避免了频繁冻结向量的性能开销，同时保证每个索引只被处理一次。
   • 所有可变向量的读写操作都严格在ST monad内部执行，类型完全匹配。

3. applyChain 逻辑优化：

   • 移除嵌套的runST，直接在当前ST上下文操作向量。
   • 写入前检查目标位置是否为0，确保每个索引仅被修改一次，符合你的需求。

内容的提问来源于stack exchange，提问作者Alfy B