小编Zaf*_*sur的帖子

我最近一两个月一直在学习Haskell，最近解决了这个编码问题。额外的挑战是在没有额外空间和线性时间内完成任务，我认为这不可能以纯函数的方式完成，所以很自然地我发现了 ST monad，我认为这将是一个很好的机会了解更多信息。不管怎样，这是我写的代码：

module FindDuplicates where\n\nimport Control.Monad (foldM)\nimport Control.Monad.ST\nimport Data.Array.ST\n\nxs = [4,3,2,7,8,2,3,1] :: [Int]\n\nfindDuplicates :: [Int] -> ST s [Int]\nfindDuplicates xs = do\n    arr <- newListArray (1, length xs) xs :: ST s (STArray s Int Int)\n\n    let go :: [Int] -> Int -> ST s [Int]\n        go acc i = do x <- abs <$> readArray arr i\n                      y <- readArray arr x\n                      if y < 0\n                          then return (x:acc)\n                          else do writeArray arr x (-y)\n …