Haskell多态数组操作

3

我正在编写很多不同的排序算法,同时也对列表和数组进行排序。有一件事情让我感到困扰,那就是我可以为列表编写一个多态排序函数,例如:

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

它会失败,并出现来自GHC的长错误消息(使用UArray Int Int版本可以正常工作)。我尝试指定{-# LANGUAGE ScopedTypeVariables #-},但这并不能消除thaw调用中类型i e的歧义。没有thaw类型的错误消息:http://hpaste.org/84910
我需要编写一个多态UArray操作,我需要什么?是否存在一些根本性限制?是否有编译器扩展可以做到这些事情?

如果您从 thaw ua 中删除类型注释,那么会得到什么错误? - dave4420
@dave4420 http://hpaste.org/84910 - Dmytro Sirenko
3个回答

3
有两个问题。首先,正如dave4420指出的那样runST需要在状态s中使alter函数具有多态性。

然而,修正这个问题会导致解决第二个问题变得不可能,即您需要一个MArray实例来进行thaw(和freeze)。您需要一个约束条件。

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

为了让它正常工作,需要选择s,因为runST是这个选择。但你不能指定这样的限制。
如果您提供特定的元素类型(IntDouble等),它就能正常工作,因为有一个...
instance MArray (STUArray s) Int (ST s) where ...

所以无论 runST 选择什么样的 sthawfreeze 的要求都能得到满足(约束条件不必声明)。此外,如果选择装箱数组而非非装箱数组,它也能正常工作,因为也存在一个。
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 操作,但会将其隐藏在调用者之外。因此,让我们通过强制在 alter 参数上使用更通用的类型来使这里对 unsafePerformIO 的使用安全:

{-# 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。)

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://dev59.com/w0vSa4cB1Zd3GeqPhtdF#2244281

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`是什么。然后,你的代码将`runST`的选择推迟到了`s`;它的类型坚持认为它有权做出选择。

我尝试通过将类型签名更改为(Ix i, Ord e, MArray (STUArray s) e (ST s)) => (forall s1. STUArray s1 i e -> ST s1 ()) -> UArray i e -> UArray i e来指定更多的上下文,但也不起作用。 - Dmytro Sirenko
Cale在#haskell IRC上建议使用以下代码:alterUArrayST :: forall i e s. (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) - Dmytro Sirenko
@EarlGray,Cale的回答解决了你的问题吗?如果没有,你导入了哪些模块? - dave4420
是的,它可以通过 RankNTypes, FlexibleContexts, ScopedTypeVariables 进行编译,但是(正如他所警告的那样),将此函数应用于其他函数仍需要大量的类型匹配工作。 - Dmytro Sirenko

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接