Editing Arrays (section)

== Unboxed arrays ==

In most implementations of lazy evaluation, values are represented at runtime as pointers to either their value, or code for computing their value. This extra level of indirection, together with any extra tags needed by the runtime, is known as a box. The default "boxed" arrays consist of many of these boxes, each of which may compute its value separately. This allows for many neat tricks, like recursively defining an array's elements in terms of one another, or only computing the specific elements of the array which are ever needed. However, for large arrays, it costs a lot in terms of overhead, and if the entire array is always needed, it can be a waste.

Unboxed arrays are more like arrays in C - they contain just the plain
values without this extra level of indirection, so that, for example,
an array of 1024 values of type Int32 will use only 4 kb of memory. 
Moreover, indexing of such arrays can be significantly faster.

Of course, unboxed arrays have their own disadvantages. First, unboxed
arrays can be made only of plain values having a fixed size - Int, Word,
Char, Bool, Ptr, Double, etc. (see the full list in the [http://www.haskell.org/ghc/docs/latest/html/libraries/array/Data-Array-Unboxed.html Data.Array.Unboxed] module).
You can even implement unboxed arrays yourself for other
simple types, including enumerations. But Integer, String and any
other types defined with variable size cannot be elements of unboxed arrays.
Second, without that extra level of indirection, all of the elements in an unboxed array must be evaluated when the array is evaluated, so you lose the benefits of lazy evaluation. Indexing the array to read just one element will construct the entire array. This is not much of a loss if you will eventually need the whole array, but it does prevent recursively defining the array elements in terms of each other, and may be too expensive if you only ever need specific values. Nevertheless, unboxed arrays are a very useful optimization
instrument, and I recommend using them as much as possible.

All main array types in the library have unboxed counterparts:

 Array - UArray          (module Data.Array.Unboxed)
 IOArray - IOUArray      (module Data.Array.IO)
 STArray - STUArray      (module Data.Array.ST)
 DiffArray - DiffUArray  (module Data.Array.Diff)

So, basically replacing boxed arrays in your program with unboxed ones
is very simple - just add 'U' to the type signatures, and you are done! Of course, if you change Array to UArray, you also need to add "Data.Array.Unboxed"
to your imports list.