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

Question

下面是 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 的约束允许这种概括？

Answer 1

array 的类 API不幸的是没有正确隐藏s状态参数。当你写 runSTUArray action , action将 s 作为输入类型参数。在 selectionSort 的类型注释中我们必须写MArray (STUArray s) a (ST s) ，但这没有意义，因为 s在运行的操作中使用的参数甚至不在此处的范围内。提s这里只是介绍一个新的不同s参数，因此有歧义错误。

constraint package 对这类事情有一个很好的解决方案。与 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通过父类(super class) 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