用ST數組寫一個多態的Haskell函數

我想在任意類型的列表上做一個函數，並做一些計算，將中間結果存儲在一個STArray中。基本上，我想要做這樣的事情（是的，這是一個愚蠢的例子）：用ST數組寫一個多態的Haskell函數

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

echoArray :: [a] -> [[a]] 
echoArray input = runST $ do 
    let n = length input 
    buf <- newListArray (0, n-1) $ map (\x->[x]) input :: ST s (STArray s Int [a]) 
    getElems buf

然而，ghci的（7.4.2版本）給出了這個壯觀的錯誤：

x.hs:7:12: 
Couldn't match type `a' with `a1' 
    `a' is a rigid type variable bound by 
     the type signature for echoArray :: [a] -> [[a]] at x.hs:5:1 
    `a1' is a rigid type variable bound by 
     an expression type signature: ST s1 (STArray s1 Int [a1]) 
     at x.hs:7:12 
Expected type: ST s (STArray s Int [a1]) 
    Actual type: ST s (STArray s Int [a]) 
In a stmt of a 'do' block: 
    buf <- newListArray (0, n - 1) $ map (\ x -> [x]) input :: 
      ST s (STArray s Int [a]) 
In the second argument of `($)', namely 
    `do { let n = length input; 
     buf <- newListArray (0, n - 1) $ map (\ x -> [...]) input :: 
       ST s (STArray s Int [a]); 
     getElems buf }'

如果我刪除類型簽名（「:: ST小號......」），我仍然得到一個不同的錯誤：

x.hs:7:12: 
No instance for (MArray a0 [a] (ST s)) 
    arising from a use of `newListArray' 
Possible fix: 
    add an instance declaration for (MArray a0 [a] (ST s)) 
In the expression: newListArray (0, n - 1) 
In a stmt of a 'do' block: 
    buf <- newListArray (0, n - 1) $ map (\ x -> [x]) input 
In the second argument of `($)', namely 
    `do { let n = length input; 
     buf <- newListArray (0, n - 1) $ map (\ x -> [x]) input; 
     getElems buf }'

如果我反而變三級出現的「一」，比方說，char，那我當然會編譯它。但是我想要一個可用於[Int]，[Char]，[Int-> Int]或其他任何類型的泛型函數。

我該怎麼辦呢？謝謝！

來源

2013-10-13 jick

也許您需要添加NoMonomorphismRestriction language pragma？ –

@ИльяРезвов不，這不會在這裏幫助，不幸的是。 –

這裏的問題是buf <-行中的類型變量a實際上與echoArray :: [a] -> [[a]]行中的a行不一樣！您可以通過打開ScopedTypeVariables和寫作

echoArray :: forall a. [a] -> [[a]]

這將給a範圍在echoArray體內的類型層次解決這個問題。

來源

2013-10-13 20:02:32

太棒了！非常感謝，修復了它，但它不知何故感覺像......黑魔法。並非所有的Haskell類型簽名默認都是「全局量化的」？爲什麼添加「全部a」突然改變了？ – jick

@jick是的，在添加'forall'之前和之後，變量'a'被普遍量化。正如你所說，唯一的區別在於範圍界定，而不是涉及什麼樣的量化。至於爲什麼'forall'是用來控制範圍界定的關鍵字，那麼就是爲了避免在語言中添加太多的關鍵字。 =） –

因此，基本上，你希望你能申報buf右側爲ST s (STArray s Int [a])，但如果你這樣做了，那麼a將是一個新的變量類型是獨立於echoArray簽名的a的。但是你希望它和a一樣。

您可以使用ScopedTypeVariables，正如@DanielWagner所示。

但有一種方法可以不使用ScopedTypeVariables或forall。

函數的簽名允許您建立參數和結果類型之間的關係。因此，不是使用簽名來約束「結果」類型，而是使用簽名來約束某個函數的類型，該函數的參數某種程度上也包含類型a。然後讓輸入推理來建立連接。這是一個解決方案，您的情況：

echoArray :: [a] -> [[a]] 
echoArray input = runST $ do 
    let n = length input 
    buf <- newSTListArray (0, n-1) $ map (\x->[x]) input 
    getElems buf 
    where newSTListArray :: (Ix i) => (i,i) -> [a] -> ST s (STArray s i a) 
     newSTListArray = newListArray

你可以看到：

newSTListArray被簡單地定義爲newListArray，所以從一個計算點是沒用的。但是，它可以使類型更加具體。
否使用ScopedTypeVariables或forall。 newSTListArray簽名中的a與echoArray的簽名中的a沒有明確關聯，但通過推斷它被強制爲相同。之所以這麼做，是因爲你的代碼沒有在你簽名中的a是孤立的，而這裏結果類型中的a與參數類型中的a綁定。

來源

2013-10-15 09:38:48 newacct

用ST數組寫一個多態的Haskell函數

回答

相關問題