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?

Daniel Fischer · Accepted Answer · 2012-02-12 20:02:06Z

3

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

a monmorphic type, say UArray (Int,Int) Int (element type could also be Word, ...)
a type monomorphic in the array type and polymorphic in the element type
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.)

edited Feb 12, 2012 at 20:02

answered Feb 12, 2012 at 17:42

Daniel Fischer

185k19 gold badges319 silver badges436 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Toymakerii Over a year ago

gist.github.com/1810229 There is the code. I think I understand what you are saying, but I am having a hell of a time trying to figure out just how to fix the signatures.

Daniel Fischer Over a year ago

Added a how to for applyWindow, the problem were the local bindings, but letting all arrays have the same type is probably desirable.

Toymakerii Over a year ago

Hot Damn! I have been fighting this for two days now, I wanted the polymorphic element types, and I danced around FlexibleInstances and ScopedTypedVariables for hours and hours. Thank you sir!

Will Ness · Accepted Answer · 2012-02-12 01:22:37Z

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.

answered Feb 12, 2012 at 1:22

Will Ness

71.6k10 gold badges105 silver badges193 bronze badges

1 Comment

Toymakerii Over a year ago

If that is the problem I need to be able to add explicit non-existential signatures within a translation rule pragma. Which I have not been successful at doing

Collectives™ on Stack Overflow

Haskell Converting from Array to Unboxed Array breaks rewrite rules

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related