Haskell ST Monad：没有 (MArray (STArray s) Int (ST s1)) 的实例

Question

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

\n\n

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                                  return acc \n\n    foldM go [] [1..length xs]\n

\n\n

这个想法是使用先决条件 1 \xe2\x89\xa4 a[i] \xe2\x89\xa4 n 并且每个元素最多出现 2 次。但代码给了我以下错误。

\n\n

FindDuplicates.hs:14:36:\n    No instance for (MArray (STArray s) Int (ST s1))\n      arising from a use of \xe2\x80\x98readArray\xe2\x80\x99\n    In the second argument of \xe2\x80\x98(<$>)\xe2\x80\x99, namely \xe2\x80\x98readArray arr i\xe2\x80\x99\n    In a stmt of a \'do\' block: x <- abs <$> readArray arr i\n    In the expression:\n      do { x <- abs <$> readArray arr i;\n           y <- readArray arr x;\n           if y < 0 then\n               return (x : acc)\n           else\n               do { writeArray arr x (- y);\n                    .... } }\n

\n\n

我希望有人能指出我正确的方向！

\n

Answer 1

在 中No instance for (MArray (STArray s) Int (ST s1))，最需要注意的是它谈论的是两个不同类型的变量s和s1。MArray除非这两个类型变量相同，否则不存在 的实例。ST这是外部纯接口的有效性的重要部分。

编译器认为涉及两个不同类型变量的原因是您在go. 该签名中的类型变量与的签名中的s类型变量不同。这是 Haskell 类型签名规则的固有部分 - 任何特定签名中的类型变量与任何其他签名中的类型变量无关。sfindDuplicates

解决此问题的最简单方法是从 中删除签名go。类型推断将获得正确的类型。

如果您想要更高级，可以使用扩展ScopedTypeVariables来允许签名go与封闭的定义共享类型变量：

{-# LANGUAGE ScopedTypeVariables #-}
module FindDuplicates where

import Control.Monad (foldM)
import Control.Monad.ST
import Data.Array.ST

xs = [4,3,2,7,8,2,3,1] :: [Int]

findDuplicates :: forall s. [Int] -> ST s [Int]
findDuplicates xs = do
    arr <- newListArray (1, length xs) xs :: ST s (STArray s Int Int)

    let go :: [Int] -> Int -> ST s [Int]
        go acc i = do x <- abs <$> readArray arr i
                      y <- readArray arr x
                      if y < 0
                          then return (x:acc)
                          else do writeArray arr x (-y)
                                  return acc 

    foldM go [] [1..length xs]

LANGUAGE顶部的编译指示启用扩展。要使用扩展，您需要在定义中使用forall. （忘记这样做是ScopedTypeVariables工作失败的最常见原因。）

在 的 类型中执行此操作后findDuplicates，它将其存储s在整个定义的范围内。s当在 类型中找到类型变量时go，它不再将其视为新类型变量，而是使其s与封闭上下文中的类型匹配。