Haskell多态阵列操作

Question

我正在写一堆不同的排序，并为列表和数组也做这些。困扰我的一件事是，我可以写列出了多态的排序功能像

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

但我当我试图为UArray就做相同的：

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 

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

我需要编写一个polymorhic UArray操作？是否有一些基金会的限制？是否有编译器扩展允许做这样的事情？

Answer 1

有两个问题。首先，如dave4420 pointed out,runST需要alter函数在状态s中是多态的。

然而，解决这个问题使得解决第二个问题成为不可能，您需要（和freeze）的MArray实例。您将需要一个约束

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和freeze的需求得到满足无论什么s被选择runST（和约束不需要说明）。

如果你选择盒装数组，而不是未装箱的，因为还存在

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参数，虽然这个参数确实会造成一些不必要的损失，但它会将其从调用者中隐藏起来。因此，让我们把使用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没有问题。）

Answer 2

更改类型声明

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是什么。您的代码然后将s选择为runST;它的类型坚持要做出选择。

Answer 3

我也被这类问题所困扰。现在我认为写这样的多态函数是不可能的。

我们可以写

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中的这类问题提供了另一种解决方法。