[Haskell-cafe] Data.Foldable UArray

[Tom Ellis]

On Fri, Feb 21, 2014 at 09:30:12PM +0100, Marcus D. Gabriel wrote:
> > Prelude> :k Data.Array.Unboxed.UArray
> > Data.Array.Unboxed.UArray :: * -> * -> *
> 
> which is why I tried my first naive solution.

Hi Marcus,

This means that 'UArray' is a type constructor of two arguments, i.e. for
types 'i' and 'e'

    UArray i e

is a type.  It is an array that is indexed by elements of type 'i' (which
would typically be something like 'Int' in practice).  It is also declaring
that ostensibly it contains unboxed values of type 'e' (which in practice
could be 'Bool', 'Char', 'Int', 'Double' and many other things besides). 
For example, a type of an unboxed array you might use could be

    UArray Int Double

an array of doubles indexed by ints.  However if you look at the definition
of 'UArray'

    http://hackage.haskell.org/package/array-0.5.0.0/docs/src/Data-Array-Base.html#UArray

you will see that the 'e' type parameter is not actually used in the
definition of the datatype!  It is a so-called "phantom type".  The datatype
doesn't "actually" contain any 'e's.  Instead it contains a ByteString into
which certain 'e's can be written in a way which is in a sense "unsafe" but
only a "safe" interface is provided.  (See below).

> I note that we have also
>
> > Prelude> :k Data.Array.IArray.IArray
> > Data.Array.IArray.IArray :: (* -> * -> *) -> * -> Constraint
> 
> This last one I do not follow.  A short explanation and/or a pointer
> to some documentation would help.

'IArray' is a typeclass, in this case essentially used as means of providing
a standard interface to arrays.  The kind signature above means that the
interface is parametrised by the array constructor (of kind * -> * -> *,
like UArray, see above) and the type of the index.  If you give 'IArray' an
array constructor and an index type you get a 'Constraint', in this case a
typeclass context which essentially provides you with an interface to access
your 'UArray' with.

However, these constructions are not suitible for making an instance of
Foldable, because Foldable would require implementing functions that are
uniform in the way they treat the type argument 'e', and as we've seen, the
usage of 'e' in the datatype and interface is far from uniform.

Hope that helps,

Tom