3

我正在编写一堆不同的类型，并为列表和数组执行此操作。困扰我的一件事是我可以为列表编写一个多态排序函数，例如

bubblesort :: (Ord a) => [a] -> [a]

但是当我尝试对UArrays 做同样的事情时：

alterUArray :: (Ix i, Ord e) => 
               (STUArray s i e -> ST s ()) -> UArray i e -> UArray i e
alterUArray alter ua = runST $ do
    mua <- thaw ua :: ST s1 (STUArray s1 i e)
    alter mua
    freeze mua

它因来自 GHC 的长错误消息而失败（一个UArray Int Int运行良好的版本）。我试图指定{-# LANGUAGE ScopedTypeVariables #-}，但这并不能消除调用中类型i e的歧义。thaw没有类型的错误消息：http thaw: //hpaste.org/84910。

编写多态UArray操作需要什么？有一些基本的限制吗？是否有允许执行此类操作的编译器扩展？

4

3 回答 3

3

有两个问题。首先，正如dave4420 所指出的，状态中runST需要alter函数是多态的s。

然而，解决这个问题就无法解决第二个问题，即您需要(and )的MArray实例。你需要一个约束thawfreeze

alterUArray :: (Ix i, Ord e, IArray UArray e, forall s. MArray (STUArray s) e (ST s)) => ...

让它工作，因为runST是选择的一个s。但是您不能指定这样的约束。

如果你给出一个特定的元素类型（Int, Double, ...），它可以工作，因为有一个

instance MArray (STUArray s) Int (ST s) where ...

因此，无论选择什么，都可以满足thaw和的要求（并且不需要说明约束）。freezesrunST

如果您选择盒装数组而不是未盒装数组，它也可以工作，因为还有一个

instance MArray (STArray s) e (ST s) where ...

因此对需要在alterUArray. （对列表元素的类型没有限制，并且列表元素是装箱的，所以装箱的数组是列表的对应关系，而不是未装箱的数组）。

如果你能忍受弄脏你的手，你可以通过替换来规避这个ST s问题IO，

alterUArray :: (Ix i, Ord e, MArray IOUArray e IO, IArray UArray e) =>
               (IOUArray i e -> IO ()) -> UArray i e -> UArray i e
alterUArray alter ua = unsafePerformIO $ do
    mua <- thaw ua
    alter mua
    freeze mua

只需要FlexibleContexts。但是，这允许传递一个错误的alter参数，该参数会做一些邪恶的IO事情，并且会对调用者隐藏它。因此，让我们unsafePerformIO通过在参数上强制使用更通用的类型来安全地使用这里alter：

{-# LANGUAGE FlexibleContexts, RankNTypes, ScopedTypeVariables #-}

import Data.Array.Unboxed
import Data.Array.IO
import System.IO.Unsafe

alterUArray :: forall i e. (Ix i, Ord e, IArray UArray e, MArray IOUArray e IO) =>
               (forall m u. MArray u e m => u i e -> m ()) -> UArray i e -> UArray i e
alterUArray alter ua = unsafePerformIO $ do
    mua <- thaw ua :: IO (IOUArray i e)
    alter mua
    freeze mua

现在我们已经给出alter了一个类型，它使得IO不使用自身就无法进行恶意操作unsafePerformIO，所以unsafePerformIO这里的使用不会引入额外的不安全性——以更多需要的扩展为代价。

（注意：虽然thaw需要获取原始数组的副本，但冻结时不需要额外的副本，这可能unsafeFreeze没有问题。）

于 2013-03-31T13:39:39.420 回答
1

我也被这样的问题困扰。现在我相信编写这样的多态函数是不可能的。

我们可以写

alterArray :: (Ix i, IArray b e, IArray a e, MArray a2 e m) => 
              (a2 i e -> m a1) -> a i e -> m (b i e)
alterArray alter ua = do
    mua <- thaw ua 
    alter mua
    freeze mua

或者

alterUArrayST :: (Ix i, IArray UArray e, MArray (STUArray s) e (ST s)) => 
                 (STUArray s i e -> ST s ()) -> UArray i e -> ST s (UArray i e)
alterUArrayST alter ua = do
    mua <- thaw ua 
    alter mua
    freeze mua

但是如果我们想摆脱ST，我们必须编写一些特定于类型的版本，例如

alterUArrayInt :: (forall s. STUArray s Int Int -> ST s ()) -> UArray Int Int -> UArray Int Int
alterUArrayInt alter ua = runST $ do
    mua <- thaw ua 
    alter mua
    freeze mua

alterUArrayFloat :: (forall s. STUArray s Int Float -> ST s ()) -> UArray Int Float -> UArray Int Float
alterUArrayFloat alter ua = runST $ do
    mua <- thaw ua 
    alter mua
    freeze mua

如果MArray有一个实例MArray (STUArray s) e (ST s)，我认为我们可以编写这样的多态函数。不幸的是，MArray没有这样的例子。

yairchu 在https://stackoverflow.com/a/2244281/779412中为此类问题提供了另一种解决方法。

于 2013-03-31T12:02:42.160 回答
0

将类型声明更改为

alterUArray :: (Ix i, Ord e) => 
               (forall s. STUArray s i e -> ST s ()) -> UArray i e -> UArray i e

并摆脱thaw ua.

您需要启用RankNTypes扩展程序（或者Rank2Types，尽管已弃用）（但您不需要这样做才能使用runST吗？我忘记了）。

说明：你原来的类型声明相当于

alterUArray :: (Ix i, Ord e) => 
               forall s. (STUArray s i e -> ST s ()) -> UArray i e -> UArray i e

这意味着alterUArray调用者可以选择是什么s。我改变的类型坚持相反，它alterUArray可以选择自己是什么s。然后，您的代码将选择sto runST; 它的类型坚持它可以做出选择。

于 2013-03-31T09:35:10.190 回答