Writing a polymorphic Haskell function with ST array

Question

I'm trying to make a function on a list of arbitrary type, and do some computation, storing the intermediate results in an STArray. Basically, I want to do something like this (yes, this is a silly example):

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

However, ghci (version 7.4.2) gives this spectacular error:

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 }'

If I remove the type signature (":: ST s..."), I still get a different error:

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 }'

If I instead change three occurrences of "a" to, say, Char, then of course I can compile it. But I want a generic function that can be used for [Int], [Char], [Int->Int], or whatever.

How can I do it? Thanks!

Answer 1

The problem here is that the type variable a in the buf <- line isn't actually the same a as in the echoArray :: [a] -> [[a]] line! You can fix this by turning on ScopedTypeVariables and writing

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

which will put a in scope at the type level inside the body of echoArray.

Answer 2

So basically, you wish that you could declare the right hand side of buf as ST s (STArray s Int [a]), but if you did it this way, then a would be a new type variable that is independent of the a in the signature of echoArray. But you want it to be the same as that a.

You could use ScopedTypeVariables, as @DanielWagner showed.

But there is a way to do it without using ScopedTypeVariables or forall.

The signature of a function allows you to establish the relationship between the parameters and result types. So instead of using a signature to constrain the type on a "result", use a signature to constrain the type on a function whose parameters somehow also contain the type a. Then let type inference to establish the connection. This is one solution to your case:

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

You can see that:

1. newSTListArray is simply defined as newListArray, so from a computational point of view it is useless. However, it serves to make the type more specific.
2. No ScopedTypeVariables or forall was used. The a in the signature of newSTListArray is not explicitly tied to the a in the signature of echoArray, but it is forced to be the same through inference. The reason that this works and your code didn't was that the a in your signature was alone, whereas here the a in the result type is tied to the a in a parameter type.