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

Question

最近一两个月我一直在学习Haskell，最近解决了this编码问题。额外的挑战是在没有额外 space 的情况下并在线性时间内完成任务，我认为这不可能以纯函数方式完成，所以自然而然地我发现了 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 如何对外部纯接口有效的重要部分。

编译器认为涉及两个不同类型变量的原因是您在 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 pragma 启用扩展。要使用扩展，您需要在定义中使用 forall 指定类型变量。（忘记这样做是 ScopedTypeVariables 无法工作的最常见原因。）

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

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

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

monads

haskell

starray

st-monad