Two almost identical functions using STArray: why does one requires FlexibleContexts, and the other does not?

Question

Consider the Haskell functions

test :: ST s [Int]
test = do
    arr <- newListArray (0,9) [0..9] :: ST s (STArray s Int Int)
    let f i = do writeArray arr i (2*i)
                 readArray arr i 
    forM [1,2] f

and

test' :: ST s [Int]
test' = do
    arr <- newListArray (0,9) [0..9] :: ST s (STArray s Int Int)
    let f = \i -> do writeArray arr i (2*i)
                     readArray arr i
    forM [1,2] f

The first requires FlexibleContexts to compile on ghci 8.10.1, the second compiles with no extra options. Why?

An answer that explains this behaviour in terms of the scope of the type variable s would be especially welcome. As a follow up, what (if any) type signature can be added to the function f to make test compile without FlexibleContexts? Finally, is there a connection with the monomorphism restriction?

If you disable the monomorphism restriction then you'll see that the second example also requires flexible contexts. — Noughtmare, Jan 22 '22 at 19:10
Please could you make this into an answer, explaining why the inferred type with the monomorphism restriction turned on (as usual) is sufficiently precise that FlexibleContexts is not required? — Mark Wildon, Jan 22 '22 at 19:20
@MarkWildon, try to figure out the type of `f` looking *only* at its definition, without context. What is it? — dfeuer, Jan 22 '22 at 20:26
Just looking at the type of `f` without context, I get `f :: (Num a) => a -> ST s a` without the monomorphism restriction and, I would guess, `f :: Integer -> ST s Integer` with the monomorphism restriction. (But I think this will refuse to typecheck, as the type of the array used is ambiguous: i.e. the context matters!) Also I suppose that in context, with the monomorphism restriction, the compiler picks `Int` rather than `Integer`. But why is this okay in context, and the more polymorphic signature not? Again, I seek an answer that makes clear the role of the type variable `s`. — Mark Wildon, Jan 22 '22 at 20:53

score 1 · Accepted Answer · answered Jan 23 '22 at 12:19

You can check which type GHC assigns to f in GHCi:

ghci> import Data.Array
ghci> import Data.Array.MArray
ghci> let arr :: STArray s Int Int; arr = undefined
ghci> :t \i -> do writeArray arr i (2*i); readArray arr i
\i -> do writeArray arr i (2*i); readArray arr i
  :: (MArray (STArray s1) Int m, MArray (STArray s2) Int m) =>
     Int -> m Int

This is more general than the type you suggest in your comments and the reason that FlexibleContexts are needed.

You can add the type signature you suggested (Int -> ST s Int) to avoid having to use FlexibleContexts:

{-# LANGUAGE ScopedTypeVariables #-}

...

test :: forall s. ST s [Int]
test = do
    arr <- newListArray (0,9) [0..9] :: ST s (STArray s Int Int)
    let 
      f :: Int -> ST s Int
      f i = do
        writeArray arr i (2*i)
        readArray arr i 
    forM [1,2] f

Note that scoped type variables and the forall s. are necessary here because you need to make sure that the s in all the type signatures refer to the same type variable and do not all introduce new type variables.

The reason that the monomorphism restriction treats your first and your second version differently is because it doesn't apply to things that look like functions. In your first version f has an argument, so it looks like a function and therefore will get a general type. In your second version f doesn't have arguments, so it doesn't look like a function which means that the monomorphism restriction forces it to have a more specific type.

Two almost identical functions using STArray: why does one requires FlexibleContexts, and the other does not?

1 Answers1