haskell - 如何概括这种就地选择排序？

以下是ST Monad中选择排序的实现。使用STUArray s Int Int将输入数组复制到thaw，然后将副本按原位排序。

selectionSort :: UArray Int Int -> UArray Int Int
selectionSort arr = runSTUArray $ do
  let (l, n) = bounds arr
  a <- thaw arr
  forM_ [l..n] $ \i -> do
    minIdx <- newSTRef i
    forM_ [i..n] $ \j -> do
      currentMin <- readSTRef minIdx
      jVal <- readArray a j
      minVal <- readArray a currentMin
      when (jVal < minVal) (writeSTRef minIdx j)
    currentMin <- readSTRef minIdx
    iVal <- readArray a i
    minVal <- readArray a currentMin
    writeArray a i minVal
    writeArray a currentMin iVal
  return a

我想使用FlexibleContexts将类型概括为：

(IArray UArray a, Ord a, Ix i, Enum i) => UArray i a -> UArray i a

但是，这导致以下类型错误：

Could not deduce (MArray (STUArray s) a (ST s))
  arising from a use of `thaw'
from the context (IArray UArray a, Ord a, Ix i, Enum i)

如何更改selectionSort的约束以允许这种概括？

最佳答案

不幸的是，array的类API无法正确隐藏s状态参数。编写runSTUArray action时，action将s类型参数作为输入。在selectionSort的类型注释中，我们将不得不编写MArray (STUArray s) a (ST s)，但这没有意义，因为在运行的操作中使用的s参数甚至不在这里。在这里提到s只是引入了一个新的不同的s参数，因此存在歧义错误。

constraint包为此类问题提供了一个不错的解决方案。使用Forall中的Data.Constraint.Forall，我们可以表示约束必须满足类型参数的任意选择。在我们的案例中，我们可以表示MArray (STUArray s) a (ST s)必须针对任意s成立，并且在ST动作内部，我们可以将量化约束实例化为所需的特定s。

{-# language UndecidableInstances, ScopedTypeVariables #-}

import Data.STRef
import Control.Monad
import Control.Monad.ST.Strict
import Data.Constraint.Forall
import Data.Constraint
import Data.Proxy

首先，我们必须创建一个包装类，可以将其插入Forall中。

class    (MArray (STUArray s) a (ST s)) => MArray' a s
instance (MArray (STUArray s) a (ST s)) => MArray' a s

现在，Forall (MArray' a)成为一个约束，我们可以从中为任意MArray' a s生成s约束，而MArray' a s则通过对MArray (STUArray s) a (ST s)约束（我们实际上需要）进行超类化来隐含。

为了方便起见，我们需要一个替代的运行器函数，该函数使s输入类型参数更明确，因此可以在正文中引用它：

runSTUArray' :: (forall s. Proxy s -> ST s (STUArray s i e)) -> UArray i e
runSTUArray' f = runSTUArray (f Proxy)

现在可以编写通用的selectionSort，我们观察到它可以专用于先前的类型：

selectionSort ::
  forall i a.
  (IArray UArray a, Ord a, Ix i, Enum i, Forall (MArray' a))
  => UArray i a -> UArray i a
selectionSort arr = runSTUArray' $ \(s :: Proxy s) -> do
  let (l, n) = bounds arr

  -- we use "inst" and a type annotation on its result to instantiate
  -- the Forall constraint to the current "s"
  case inst of
    (Sub (Dict :: Dict (MArray' a s))) -> do

      a <- thaw arr
      forM_ [l..n] $ \i -> do
        minIdx <- newSTRef i
        forM_ [i..n] $ \j -> do
          currentMin <- readSTRef minIdx
          jVal <- readArray a j
          minVal <- readArray a currentMin
          when (jVal < minVal) (writeSTRef minIdx j)
        currentMin <- readSTRef minIdx
        iVal <- readArray a i
        minVal <- readArray a currentMin
        writeArray a i minVal
        writeArray a currentMin iVal
      return a

selectionSort' :: UArray Int Int -> UArray Int Int
selectionSort' = selectionSort