Haskell Converting from Array to Unboxed Array breaks rewrite rules

Question

I am trying to convert my program from using Data.Array to Data.Array.Unboxed.

As a quick side note: several places state that I can change "Array" to "UArray" in my code and ADD an import of Data.Array.Unboxed, however I am not mixing both types of arrays so I just imported Data.Array.Unboxed instead of Data.Array, is this sufficient?

When I make the switch the following rewrite rule breaks:

{-# RULES
    "applyWindow/applyWindow" forall win1 win2 image. 
                                     applyWindow win1 
                                                 (applyWindow win2 
                                                 image) = 
                                     applyWindow (indexMult win1 win2) 
                                                            image
  #-}

Here win1 win2 and image should all be UArrays. However, this fails to compile with the follwing errors.

FIPlib/Core.hs:229:99:
    Ambiguous type variables `e0', `a0' in the constraint:
      (IArray a0 e0) arising from a use of `applyWindow'
    Probable fix: add a type signature that fixes these type variable(s)
    In the expression: applyWindow (indexMult win1 win2) image
    When checking the transformation rule "applyWindow/applyWindow"

FIPlib/Core.hs:229:99:
    Ambiguous type variables `e0', `a2' in the constraint:
      (IArray a2 e0) arising from a use of `applyWindow'
    Probable fix: add a type signature that fixes these type variable(s)
    In the expression: applyWindow (indexMult win1 win2) image
    When checking the transformation rule "applyWindow/applyWindow"

FIPlib/Core.hs:229:112:
     Ambiguous type variables `e0', `a1' in the constraint:
      (IArray a1 e0) arising from a use of `indexMult'
    Probable fix: add a type signature that fixes these type variable(s)
    In the first argument of `applyWindow', namely
      `(indexMult win1 win2)'
    In the expression: applyWindow (indexMult win1 win2) image
    When checking the transformation rule "applyWindow/applyWindow"

What makes this ambiguous? Why does this break when it works with Data.Array?

Answer 1

The problem is that Data.Array.Unboxed reexports Data.Array.IArray, and hence the IArray class for the immutable-array interface, but Data.Array doesn't (it doesn't even import it). So if you use functions like bounds, accumArray, array etc. with only Data.Array imported, they are monomorphic in the array type, thus no ambiguity arises (the polymorphism in the element type apparently doesn't pose a problem here, it would with suitable type class constraints). But if you import Data.Array.Unboxed, all these functions get an IArray a e constraint, and thus the rewriting might involve different array types, thus breaks. You need to fix the types with type signatures, on the functions or int the rule. How exactly to solve this I cannot say without seeing the code.

Note: Type checking has changed with 7.4, with ghc-7.4.1, the code without the rule doesn't compile without type signatures if importing Data.Array.Unboxed.

To fix the types, so that the rule doesn't run into ambiguity, you have to give type signatures

• on the top-level, to applyWindow,
• to the two local bindings of paddedImage and filteredPaddedImage.

The probably desired and most reasonable is for all involved arrays to have the same type, that can be

1. a monmorphic type, say UArray (Int,Int) Int (element type could also be Word, ...)
2. a type monomorphic in the array type and polymorphic in the element type
3. a type ploymorphic in both

For 1., you simply have to add the signatures, applyWindow :: T -> T -> T and xxImage :: T (where T is the desired type). For 2., you have to add two language extensions, FlexibleContexts and ScopedTypeVariables, then applyWindow would get the signature

applyWindow :: forall e. (Num e, IArray UArray e)
            => UArray (Int,Int) e -> UArray (Int,Int) e -> UArray (Int,Int) e

and the local bindings would get the signature xxImage :: UArray (Int,Int) e. FlexibleContexts is needed to allow the occurrence of UArray in the constarint, and ScopedTypeVariables is necessary to bring the element type into scope so that paddedImage and filteredPaddedImage can get type signatures at all. For 3., only ScopedTypeVariables is needed, the type signature of applyWindow would then be

applyWindow :: forall a e. (Num e, IArray a e) => ...

Another method to force all arrays to the same type is using asTypeOf or putting them all into a list (unused local binding), but IMO type signatures are preferable.

Once all types are fixed (they need not necessarily be the same, but the type of the local bindings must be determined by the argument and result types, possibly the argument types alone), the rule should type check. (It may be necessary to fix types in indexMult too.)

Answer 2

I've received exactly same error message (about IArray etc.) when I tried running this code without the explicit type signature for the array (UArray Int Bool in that case), just with the Data.Array.Unboxed import. When I added the signature all was OK. Maybe this will help you too.