Can Functor instance be declared with additional type restriction for function

Question

I'm working on porting GHC/Arr.hs into Frege.

Array is defined:

data Array i e = Array{u,l::i,n::Int,elems::(JArray e)}

There is function:

amap :: (Ix i, ArrayElem e) => (a -> b) -> Array i a -> Array i b

Now, I don't know how to define Functor instance for it, because

instance (Ix i) => Functor (Array i) where
    fmap = amap

But compiler complains that inferred type is more constrained that expected, what seems true. Can I make Array an functor with restrction for functions ArrayElem -> ArrayElem?

Answer 1

No, this is not possible.

If you base Array on JArray and want a functor instance, you must not use any functions that arise the ArrayElem (or any other additional) context.

Another way to say this is that you cannot base Array on type safe java arrays, but must deal with java arrays of type Object[]. Because, as you have without doubt noted, the ArrayElem type class is just a trick to be able to provide the correct java type on creation of a java array. This is, of course, important for interfacing with Java and for performance reasons.

Note that there is another problem with type safe java arrays. Let's say we want to make an array of Double (but the same argument holds for any other element type). AFAIK, Haskell mandates that Arrays elements must be lazy. Hence we really cannot use the java type double[] (to which JArray Double would be the Frege counterpart) to model it. Because, if we would do this, every array element would have to be evaluated as soon as it is set.

For this reason, I suggest you use some general custom array element type, like

data AElem a = AE () a 
mkAE = A () 
unAE (AE _ x) = x
derive ArrayElement AElem

and change your definition:

data Array i e = Array{u,l::i,n::Int,elems::(JArray (AElem e))}

Now, your functor instance can be written, because the ArrayElem constraint does not arise, because when you access the elems array, the compiler knows that you have AElem elements and can and will supply the correct instance.

In addition, construction of AElems and usage of AElems as actual array elements does not impose strictness on the actual value.

Needless to say, the user of the Array module should not (need to) know about those implementation details, that is, the AElem type.