3
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.
1
  • 1
    What do you expect getIndex (putIndex emptyArray 1 3) 2 to be, rather than an error? You haven’t put anything at index 2. Commented May 31, 2015 at 16:46

2 Answers 2

6

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
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for your reply. The substitution helps a lot. So in this example an array is a cascade of putIndex functions and a getIndexcall just specifies the j value to look through the if-then-elseconstruct. Which means that an emptyArray foo call will always appear (and fire an error) if no putIndex foo array call was done.
@froehli Correct, it's a big chain of if statements until emptyArray is hit.
4
  1. ar' :: Int -> a
  2. always (there is only the putIndex ar i v pattern and this will match always)
  3. well j == i if you call the resulting function/array at index i (it's the i from the call to putIndex - j is the argument for the local function ar')
  4. otherwise the old array/function ar is used (you see you change the array at just the index i = j
  5. every index in emptyArray will generate an error - with putIndex you change this here for i = 1 but afterwards you call it for i= 2 so it will use the definition of emptyArray (your otherwise case above) which is the error
  6. same situation as in 5 but here you call it with i = 1 which you putIndex to 3

Maybe you understand it like this: emptyArray is a function that always errors

You can then use putIndex to get a new array/function based on it's first argument that will do just the same as this argument - only at index i it will now return v - for all other indizes i it will return ar i (the old function/array at index i).

getIndex really is just calling the function/array for at an index

Here is why getIndex (putIndex emptyArray 1 3) 2 is an error:

getIndex (putIndex emptyArray 1 3) 2
= (putIndex emptyArray 1 3) 2
{ inside putIndex you get i = 1, v = 3 and j = 2 here }
= emptyIndex 2
= error ...

but for getIndex (putIndex emptyArray 1 3) 1 it's:

getIndex (putIndex emptyArray 1 3) 1
= (putIndex emptyArray 1 3) 1
{ inside putIndex you get i = 1, v = 3 and j = 1 here - so the `j == 1` case}
= 3

1 Comment

thanks for your reply. Your substitution helped to understand where the index comes from.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.