Array in Haskell defined with type (not data)

Question

type Array a = Int -> a

emptyArray :: Array a
emptyArray i =
  error ("Access to non-initialized index " ++ show i)

putIndex :: Array a -> Int -> a -> Array a
putIndex ar i v = ar'
 where ar' j | j==i      = v
             | otherwise = ar j

getIndex :: Array a -> Int -> a
getIndex a i = (a i)

I don't understand the emptyArray and putIndex function. Problems are:

• what is the type of ar'
• when does the ar' pattern match?
• when is j==i?
  • v is of the type a or? In that case it would not return an array.
• what happens in otherwise = ar j
• why does getIndex (putIndex emptyArray 1 3) 2 generate an error
  • getIndex (putIndex emptyArray 1 3) 1 returning 3 seems to be clear.

Answer 1

Instead of answering all of your questions directly, I'll try to give an explanation to the rationale behind the Array a type here.

Arrays can be thought of as a data structure that has particular properties, namely that given an index it can return a value associated with that index. This means that we can characterize an array by describing what values are associated with particular indexes, and this sounds very much like a function mapping an input (the index) to an output (the value at that index). Hence, an array can be thought of as no different from a function, provided you don't want to know the length or what indices are valid. This is a rather limiting definition of an array, but as a learning exercise it's important to see how data structures can be turned into functions by considering what their most important operations are.

what is the type of ar'

Look at the type signature:

putIndex :: Array a -> Int -> a -> Array a
putIndex    ar         i      v  = ar'

So ar :: Array a, i :: Int, v :: a, andar' :: Array a`.

when does the ar' pattern match?

I assume you mean when does the definition of ar' get used. ar' is an Array a, which means it's a function Int -> a. Which means it gets used whenever getIndex is called on it.

when is j == i? v is the type of a? In that case it would not return an array

Look carefully at the definition of putIndex. ar' is the return value of putIndex, not v. v is the return value of ar' when j == i. v has type a, as you can tell from the type signature of putIndex. putIndex is a function that augments an existing function ar, by adding a check first for when i == j.

what happens in otherwise = ar j

If j /= i, then instead of returning v (the new value being associated with the index i), it looks up the value at index j in the original ar. This might be more clearly stated as

putIndex originalArray indexToSet newValue = newArray
    where
        newArray j
            | j == indexToSet = newValue
            | otherwise       = getIndex originalArray j

why does getIndex (putIndex emptyArray 1 3) 2 generate an error?

Essentially, you can turn index lookup into a bunch of nested if statements:

putIndex emptyArray i0 x0  ==>  \i -> if i == i0
                                    then x0
                                    else emptyArray i

putIndex (
    putIndex emptyArray i0 x0
    ) i1 x1                ==>  \i -> if i == i1
                                    then x1
                                    else if i == i0
                                            then x0
                                            else emptyArray i

putIndex (
    putIndex (
        putIndex emptyArray i0 x0
        ) i1 x1
    ) i2 x2                ==>  \i -> if i == i2
                                    then x2
                                    else if i == i1
                                            then x1
                                            else if i == i0
                                                    then x0
                                                    else emptyArray i

And so on, adding a new layer of if-then-else for every new putIndex. For your specific example

putIndex emptyArray 1 3  ==>  \i -> if i == 1
                                    then 3
                                    else emptyArray i

Then

getIndex (putIndex emptyArray 1 3) 2

is equivalent to the expression

if 2 == 1 then 3 else emptyArray 2