haskell - 就地多态快速排序中的 STUArray 类型参数

Question

我想实现一个多态快速排序。我想具体说明一下IArray UArray a => [a] -> [a] 中的 type a 和 ST (STUArray s Int a) 是相同类型。我怎样才能做到这一点？

{-# LANGUAGE FlexibleContexts #-}
module Quicksort where

import Control.Monad.ST (ST)
import Data.Array.ST (runSTUArray, newListArray, STUArray)
import Data.Array.IArray (elems)
import Data.Array.Unboxed (UArray, IArray)

quicksort :: IArray UArray a => [a] -> [a]
quicksort l = elems $ runSTUArray $
  do newListArray (0, 9) l :: ST s (STUArray s Int a)

Answer 1

您可以通过启用 ScopedTypeVariables 和 supplying an explicit forall 来解决下一个错误。在顶级类型签名中:

quicksort :: forall a. IArray UArray a => [a] -> [a]

然后您会发现您的 STUArray 不是 MArray 的实例，因为有 no instance对于任意a。如果将其设置为 Int，它将编译。

当然，明显缺乏此类实例的原因是，未装箱数组只能包含unboxeable值，该值是原始类型，一个详尽的名册，您可以在 the relevant documentation 中查看。 .