Clever Geek Handbook

Haskell array defined with type (not data)

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 function of emptyArray

and putIndex

. Problems:

  • What is the type of ar '
  • when does the pattern ar 'match?
  • when j==i

    ?
    • v

      is of type a

      or? In this case, it will not return an array.
  • what happens differently = ar j
  • why getIndex (putIndex emptyArray 1 3) 2

    generates an error
    • getIndex (putIndex emptyArray 1 3) 1

      return 3 seems clear.
+3


source to share


2 answers


Instead of answering all your questions directly, I will try to provide an explanation of the type rationale Array a

here.

Arrays can be thought of as a data structure that has certain properties, namely that given an index, it can return the value associated with that index. This means that we can characterize an array by describing which values ​​are associated with specific indices, and this is very similar to a function that maps an input (index) to an output (a value at that index). Hence, an array can be thought of as no different from a function if you don't want to know the length or what indices are valid. This is a rather limited definition of an array, but as an educational exercise, it is important to see how data structures can be turned into functions by considering what their most important operations are.

what is the type ar'

Look at a signature like:

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

So ar :: Array a

, i :: Int

, v

:: a , and

ar ':: the Array a`.

when ar'

does the pattern match ?

I assume you mean when the definition is used ar'

. ar'

is Array a

, which means its function Int -> a

. This means that it is used when it is called getIndex

.

when j == i

? v

- type a

? In this case, it will not return an array

Look closely at the definition putIndex

. ar'

is the return value putIndex

, not v

. v

is the return value ar'

when j == i

. v

has a type a

, as you can tell from the type signature putIndex

. putIndex

is a function that complements an existing function ar

by adding a check first when i == j

.

what's going on in otherwise = ar j



If j /= i

, instead of returning v

(the new value is associated with the index i

), it looks for the value in the index j

in the original ar

. It can be more clearly stated as

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

Why is it getIndex (putIndex emptyArray 1 3) 2

generating an error?

Essentially, you can convert an index search 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 if-then-else

for each new one 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 expression

if 2 == 1 then 3 else emptyArray 2
+6


source


  • ar' :: Int -> a

  • always (only a pattern exists putIndex ar i v

    and this will always match)
  • well j == i

    if you call the resulting function / array at index i

    (this is i

    from the call putIndex

    - j

    is an argument to the local function ar'

    )
  • otherwise the old array / function is used ar

    (you see that you are changing the array with only the indexi = j

  • each index in emptyArray

    generates an error - with using putIndex

    you change this here to i = 1

    , but then you call it for i= 2

    , so it will use the definition emptyArray

    (yours otherwise

    above) which is the error
  • in the same situation as in 5, but here you call it i = 1

    which you are putIndex

    up to 3

Perhaps you understand it this way: emptyArray

is a function that alwayserrors

You can then use putIndex

to get a new array / function based on its first argument, which will do the same as that argument - only in the index i

it will return v

- for all other indices i

it will return ar i

(the old function / array at index i).

getIndex

really just calls the function / array for the index



This is why it 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

this:

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
+4


source






More articles: