Mutable Arrays

Mutable states are typically found in imperative programming languages like C or Java, but they are not commonly used in purely functional languages such as Haskell. However, many algorithms are described using pseudocode that includes mutable states. To make it easier to implement such algorithms in Keelung, we have included mutable arrays in the language.

Type of Mutable Arrays

The general form of the type of a mutable array is ArrM t, where t represents the type of elements that the mutable array can store. Currently, t can only be one of the following types:

• Field: Field elements

• Boolean: Booleans

• UInt: Unsigned integers with bit width w

• ArrM a: mutable arrays of any kind

Here are some examples of types of mutable arrays:

type	meaning
ArrM Field	An array of Field elements
ArrM Boolean	An array of Booleans
ArrM (ArrM Field)	An array of arrays of Field elements
ArrM (ArrM Boolean)	An array of arrays of Booleans

Construction / Conversion

From Haskell lists to mutable arrays

thaw takes a list of Values and process it into an Array.

thaw :: [t] -> Comp (ArrM t)

Note that because toArrayM is a statement. The resulting array of type ArrM t is wrapped in Comp. We can extract the array by using do-notation like this:

func = do 
    array <- toArrayM [3, 4, 5] -- array :: ArrM Number
    ...

This way, array would have type ArrM Number in the scope.

From Haskell lists

thaw :: [t] -> Comp (ArrM t)

Here are some helper functions of higher-dimension:

thaw2 :: [t] -> Comp (ArrM (ArrM t))
thaw3 :: [[t]] -> Comp (ArrM (ArrM (ArrM t)))

To Haskell lists

freeze works as the inverse of toArrayM. It takes a Keelung mutable array and converts it into a list.

freeze :: ArrM t -> Comp [t]

Here are some helper functions of higher-dimension:

freeze2 :: ArrM (ArrM t) -> Comp [[t]]
freeze3 :: ArrM (ArrM (ArrM t)) -> Comp [[[t]]]

Functions

Access

accessM :: ArrM t -> Int -> Comp t

Values within an array are indexed by an integer, starting from 0.

accessM takes an array and an Int as the index and returns the corresponding value.

func = do 
    array <- toArrayM [3, 4, 5]
    x <- accessM array 0          -- `x` should be equal to `3`
    ...

Update

updateM :: ArrM t -> Int -> t -> Comp ()

updateM is very much like accessM, but it takes an extra value to replace the corresponding entry in the array. update only works on mutable arrays.

func = do 
    array <- toArrayM [3, 4, 5]
    updateM array 2          
    -- `array` should be equal to `[2, 4, 5]` at this stage
    ...

Length

lengthOf :: ArrM t -> Int

lengthOf returns the length of an array.