Expressing semantics of an array as a function An assignment questions asks the following:


  Consider an array 'var a : array[1..10] of real'.  Express the
  semantics of this array as a function, defining the domain and
  codomain (you might also be able to write the rule).  In this
  programming language, the subrange '1..10' is viewed as a genuine
  type, so we can comfortably say that 'a[13]' is a type error.


I've come up with a semantic that works as a function, that is: f(a[$x$]) -> $y$ where $x$ is a type defined by the numbers $1$ to $10$ and $y$ is the set of all Real numbers. Does this seems correct?

Would there be any difference if I wrote the function in the opposite way, that is: f($y$) -> a[$x$] ?
It makes little sense to think about how we are to encode an array as a function without explaining how we intend to implement the basic array operations. The characteristic property of an array is that we can


access the $i$-th element, and
set the $i$-th element.


In addition, certain equations must be satisfied. For example, if we look up the $i$-th element twice in a row, we will see the same value, etc. (These equations can be looked up in any standard source on the state monad.)

Now, it is quite obvious that an array can be encoded as a function. But we also have to implement get and set. Here is how we might do it in Haskell.

-- An array is represented as a function from integers to floats.
type Array = Int -&gt; Float                                                   

-- create a new array all of whose elements are initialized to 0.0                  
new :: () -&gt; Array                                                          
new () = \i -&gt; 0.0                                                          

-- get a i returns the i-th element of aray a                               
get :: Array -&gt; Int -&gt; Float                                                
get a i = a i                                                               

-- set a i x returns the array a, but with i-th element set to x            
set :: Array -&gt; Int -&gt; Float -&gt; Array                                       
set a i x = \j -&gt; if j == i then x else a j


We are not checking and bounds here, which we should. It may seem a bit unusual that set returns a new array, but there really is no way of modifying an existing one in a purely functional setting. Haskell has the so-called "monadic style" of programming which makes it much easier to work with this sort of encoding (although I wouldn't recommend the encoding for a real appliaction).