Операции полиморфного массива 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 #-}, но это не устраняет неоднозначность типов i e в вызове thaw. Сообщение об ошибке без типа thaw: http://hpaste.org/84910.

Что нужно для написания полиморфной операции UArray? Существуют ли фундаментальные ограничения? Существуют ли расширения компилятора, которые позволяют делать такие вещи?

Answer 1

Есть две проблемы. Во-первых, поскольку dave4420 pointed out, runST нуждается в функции alter, чтобы быть полиморфной в состоянии s.

Устранение этого, тем не менее, делает невозможным решение второй проблемы, что вам нужен пример MArray для thaw (и freeze). Вы должны были бы ограничение

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, который делает нечестный файл 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 без проблем.)

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 получает выбрать то, что 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.