3

过去一两个月我一直在学习 Haskell，最近解决了这个编码问题。额外的挑战是在没有额外空间和线性时间的情况下完成任务，我认为这不可能以纯粹的功能方式完成，所以我自然而然地发现了 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);
                    .... } }

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

4

1 回答 1

5

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

编译器认为涉及两个不同类型变量的原因是您将类型签名放在go. 该s签名中的类型变量s与 的签名中的类型变量不同findDuplicates。这是 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在整个定义的范围内。s在 的 类型中查找类型变量时go，不再将其视为新类型变量，而是使其与s封闭上下文中的类型匹配。

于 2017-09-11T03:01:34.657 回答