STUArray với loại đa hình

Question

Tôi muốn triển khai thuật toán bằng cách sử dụng ST đơn nguyên và STUArray s và tôi muốn nó có thể hoạt động với cả hai dữ liệu Float và Double.

Tôi sẽ giải thích về một ví dụ đơn giản hơn: tính toán số scanl (+) 0 đã ghi nhớ (Tôi biết nó có thể được giải quyết mà không cần STUArray, chỉ sử dụng làm ví dụ).

{-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-} 

import Control.Monad 
import Control.Monad.ST 
import Data.Array.Unboxed 
import Data.Array.ST 

accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a 
accumST vals = (!) . runSTUArray $ do 
    arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int a) 
    forM_ (zip vals [1 .. length vals]) $ \(val, i) -> 
    readArray arr (i - 1) 
    >>= writeArray arr i . (+ val) 
    return arr 

này không thành công với:

Could not deduce (MArray (STUArray s) a (ST s)) from the context() 
    arising from a use of 'newArray' 
Possible fix: 
    add (MArray (STUArray s) a (ST s)) to the context of 
    an expression type signature 
    or add an instance declaration for (MArray (STUArray s) a (ST s)) 

Tôi không thể áp dụng các gợi ý "có thể sửa chữa". Bởi vì tôi cần phải thêm một số thứ như (forall s. MArray (STUArray s) a (ST s)) vào ngữ cảnh, nhưng không thể thực hiện được điều này ..

Answer 1

Thật không may, hiện tại bạn không thể tạo ngữ cảnh yêu cầu một mảng không có hộp được cung cấp cho một loại cụ thể. Ràng buộc định lượng không được phép. Tuy nhiên, bạn vẫn có thể thực hiện những gì bạn đang cố gắng làm, (với lợi thế bổ sung là có các phiên bản mã kiểu cụ thể.) Đối với các hàm dài hơn, bạn có thể thử tách các biểu thức chung để mã lặp lại càng nhỏ càng tốt .

{-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-} 
module AccumST where 

import Control.Monad 
import Control.Monad.ST 
import Data.Array.Unboxed 
import Data.Array.ST 
import Data.Array.IArray 

-- General one valid for all instances of Num. 
-- accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a 
accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a 
accumST vals = (!) . runSTArray $ do 
    arr <- newArray (0, length vals) 0 :: (Num a) => ST s (STArray s Int a) 
    forM_ (zip vals [1 .. length vals]) $ \(val, i) -> 
    readArray arr (i - 1) 
    >>= writeArray arr i . (+ val) 
    return arr 

accumSTFloat vals = (!) . runSTUArray $ do 
    arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int Float) 
    forM_ (zip vals [1 .. length vals]) $ \(val, i) -> 
    readArray arr (i - 1) 
    >>= writeArray arr i . (+ val) 
    return arr 

accumSTDouble vals = (!) . runSTUArray $ do 
    arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int Double) 
    forM_ (zip vals [1 .. length vals]) $ \(val, i) -> 
    readArray arr (i - 1) 
    >>= writeArray arr i . (+ val) 
    return arr 

{-# RULES "accumST/Float" accumST = accumSTFloat #-} 
{-# RULES "accumST/Double" accumST = accumSTDouble #-} 

Phiên bản Hộp Bọc Generic (mà không hoạt động) sẽ có một loại hạn chế như sau:

accumSTU :: forall a. (IArray UArray a, Num a, 
    forall s. MArray (STUArray s) a (ST s)) => [a] -> Int -> a 

Bạn có thể đơn giản hóa như sau:

-- accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a 
accumST :: forall a. (IArray UArray a, Num a) => [a] -> Int -> a 
accumST vals = (!) . runSTArray $ do 
    arr <- newArray (0, length vals) 0 :: (Num a) => ST s (STArray s Int a) 
    accumST_inner vals arr 

accumST_inner vals arr = do 
    forM_ (zip vals [1 .. length vals]) $ \(val, i) -> 
    readArray arr (i - 1) 
    >>= writeArray arr i . (+ val) 
    return arr 

accumSTFloat vals = (!) . runSTUArray $ do 
    arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int Float) 
    accumST_inner vals arr 

accumSTDouble vals = (!) . runSTUArray $ do 
    arr <- newArray (0, length vals) 0 :: ST s (STUArray s Int Double) 
    accumST_inner vals arr 

{-# RULES "accumST/Float" accumST = accumSTFloat #-} 
{-# RULES "accumST/Double" accumST = accumSTDouble #-} 

Answer 2

Vì vậy, đây là workaround tôi đang đi với bây giờ - tạo ra một typeclass mới cho các loại mà (forall s. MArray (STUArray s) a (ST s)):

class IArray UArray a => Unboxed a where 
    newSTUArray :: Ix i => (i, i) -> a -> ST s (STUArray s i a) 
    readSTUArray :: Ix i => STUArray s i a -> i -> ST s a 
    writeSTUArray :: Ix i => STUArray s i a -> i -> a -> ST s() 

instance Unboxed Float where 
    newSTUArray = newArray 
    readSTUArray = readArray 
    writeSTUArray = writeArray 

instance Unboxed Double where 
    newSTUArray = newArray 
    readSTUArray = readArray 
    writeSTUArray = writeArray 

Trong khi tôi không hoàn toàn hài lòng với điều này, tôi thích nó trên các quy tắc bởi vì:

• quy tắc phụ thuộc vào tối ưu hóa
• quy tắc không thực sự phải thay đổi thuật toán (?). trong trường hợp này, chúng sẽ là mảng được đóng hộp có hành vi rất khác nhau liên quan đến sự lười biếng, v.v.