How can I generalize this choice of place in place?

Question

The following is a sort implementation in STMonad. The input array is copied to STUArray s Int Intc thaw, then the copy is sorted in place.

selectionSort :: UArray Int Int -> UArray Int Int
selectionSort arr = runSTUArray $ do
  let (l, n) = bounds arr
  a <- thaw arr
  forM_ [l..n] $ \i -> do
    minIdx <- newSTRef i
    forM_ [i..n] $ \j -> do
      currentMin <- readSTRef minIdx
      jVal <- readArray a j
      minVal <- readArray a currentMin
      when (jVal < minVal) (writeSTRef minIdx j)
    currentMin <- readSTRef minIdx
    iVal <- readArray a i
    minVal <- readArray a currentMin
    writeArray a i minVal
    writeArray a currentMin iVal
  return a

Using FlexibleContexts, I would like to generalize this type to:

(IArray UArray a, Ord a, Ix i, Enum i) => UArray i a -> UArray i a

However, this causes the following type error:

Could not deduce (MArray (STUArray s) a (ST s))
  arising from a use of `thaw'
from the context (IArray UArray a, Ord a, Ix i, Enum i)

How to change restrictions selectionSortto allow this generalization?

Answer 1

API- array, , s. runSTUArray action, action s. selectionSort MArray (STUArray s) a (ST s), , s, , . s s, , .

constraint . Forall Data.Constraint.Forall , . , MArray (STUArray s) a (ST s) s, ST s, .

{-# language UndecidableInstances, ScopedTypeVariables #-}

import Data.STRef
import Control.Monad
import Control.Monad.ST.Strict
import Data.Constraint.Forall
import Data.Constraint
import Data.Proxy

-, Forall.

class    (MArray (STUArray s) a (ST s)) => MArray' a s
instance (MArray (STUArray s) a (ST s)) => MArray' a s

Forall (MArray' a) , MArray' a s s, MArray' a s MArray (STUArray s) a (ST s) ( ).

, s , :

runSTUArray' :: (forall s. Proxy s -> ST s (STUArray s i e)) -> UArray i e
runSTUArray' f = runSTUArray (f Proxy)

selectionSort , , :

selectionSort ::
  forall i a.
  (IArray UArray a, Ord a, Ix i, Enum i, Forall (MArray' a))
  => UArray i a -> UArray i a
selectionSort arr = runSTUArray' $ \(s :: Proxy s) -> do
  let (l, n) = bounds arr

  -- we use "inst" and a type annotation on its result to instantiate
  -- the Forall constraint to the current "s"
  case inst of
    (Sub (Dict :: Dict (MArray' a s))) -> do

      a <- thaw arr
      forM_ [l..n] $ \i -> do
        minIdx <- newSTRef i
        forM_ [i..n] $ \j -> do
          currentMin <- readSTRef minIdx
          jVal <- readArray a j
          minVal <- readArray a currentMin
          when (jVal < minVal) (writeSTRef minIdx j)
        currentMin <- readSTRef minIdx
        iVal <- readArray a i
        minVal <- readArray a currentMin
        writeArray a i minVal
        writeArray a currentMin iVal
      return a

selectionSort' :: UArray Int Int -> UArray Int Int
selectionSort' = selectionSort