Haskell ST Monad: Нет экземпляра для (MArray (STArray s) Int (ST s1))

Question

Я изучал Haskell в течение последнего месяца или двух, и недавно решил эту проблему кодирования. Дополнительная задача заключалась в том, чтобы выполнить задачу без дополнительного пространства и в линейном времени, что я не думал, что это возможно сделать чисто функциональным способом, поэтому, естественно, я узнал о монаде ST и подумал, что это будет хорошей возможностью. чтобы узнать больше об этом. В любом случае, вот код, который я написал:

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 в этой подписи не совпадает с переменной типа 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 Прагма в верхней части позволяет расширение. Чтобы использовать расширение, вам нужно указать переменные типа в определении с forall, (Забыв сделать это, самая распространенная причина ScopedTypeVariables не работать.)

После этого в типе findDuplicatesэто хранит что s в объеме по всему определению. При поиске переменной типа s в типе go, он больше не обрабатывает его как переменную нового типа и делает его соответствующим типу s в окружающем контексте вместо этого.