Haskell ST Monad : No instance for (MArray (STArray s) Int (ST s1))

Question

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

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 :: [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]

思路是利用前提条件1≤a[i]≤n，每个元素最多出现2次。但是代码给我以下错误。

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

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

Answer 1

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

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

解决此问题的最简单方法是从 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 存储在整个定义的范围内。当在go的类型中找到类型变量s时，不再将其视为一个新的类型变量，并使其与类型s匹配> 而不是在封闭的上下文中。