Haskell and Data.Array.//: why is this type correct?

user_1929678 0
Viewed 116

Creating a two-dimensional array:

import Data.Array
arr = listArray ((1, 1), (10, 10)) [1..]  -- :: (Ix i, Num i, Num e, Enum e) => Array i e

// can be used to update a value. You need to provide a list of tuples with an index and a value. Since our index is a two-tuple, the type needs to be [((a, b), e)].

 arr // _  -- _ :: [((a, b), e)]

Now I used [(1, 999)] by accident to update the first value. Of course it should have been [((1,1), 999)]. However, the mistake turned out to be type-correct!

 arr2 = arr // [(1, 999)]
 arr2  -- :: (Ix a, Ix b, Enum e, Num a, Num b, Num e, Num (a, b)) => Array (a, b) e

It hangs when I try to evaluate arr2, but I still wonder why this is type correct.

haskell
3 Answers

It says in the result type constraints Num (a, b). That is, this is only type correct if a tuple of numbers is itself a number. Someone could write that instance, and if they did then 1 could be interpreted as a tuple to index into the array with.

user_6254030

The key is buried in the type signature you quoted. It's this part:

Num (a, b)

Haskell type class instances have an "open world" assumption. The compiler doesn't know you're not going to define an instance Num (a, b) (or the same instance with constraints on a and/or b) in another module that you import. As soon as you do, then [(1, 9999)] has the correct type, because 1, like all integer literals, has type (Num t) => t, in other words it can be of any type for which there exists an instance of Num. If you make an instance Num (a, b) (or similar) then, as strange as it may look at first sight, it's perfectly correct to say that 1 has type (or at least might have type) (a, b).

user_84750540

The type signature explains it:

arr2  -- :: (Ix a, Ix b, Enum e, Num a, Num b, Num e, Num (a, b)) => Array (a, b) e

It assumes that the tuple (a, b) is a Number as well (the Num (a, b) part). So it interpets 1 as a number literal that can be converted, with fromInteger :: Num a => Integer -> a, to a 2-tuple of type (a, b), and thus will represent the index.

By default a 2-tuple is not an instance of Num. You can make a 2-tuple an instance of Num, but to what would 1 map here? If you thus later aim to obtain an array that is sensical, the type checker will not find what values to fill in for a, b, etc.

user_675790
Related