Keelung
Website
  • Hello, Keelung
  • Getting Started
    • Getting Started
    • Keelung Basics
  • Language Manual
    • Values & Expressions
      • Field elements
      • Booleans
      • Unsigned Integers
      • Built-in Parameterized Types
      • Advanced: Custom Types & Generic Instances
    • Statements
      • Input / Output
      • Assertions
      • Reusing existing computation
      • Mutable Arrays
    • Commands
    • Supported Fields
  • How-to Guides
    • Installation
    • Troubleshooting
    • Starting a Keelung project from scratch
  • Examples
    • Building a zkSNARK Application with Keelung: Merkle tree membership
    • Poseidon Hash Function
    • Sudoku
  • Downloads
    • Binaries
  • Integrations with Snarkjs
    • Generate Snakrjs-compatible R1CS and witness
Powered by GitBook
LogoLogo

Copyright © 2023 BTQ

On this page
  • Type of Mutable Arrays
  • Construction / Conversion
  • From Haskell lists to mutable arrays
  • From Haskell lists
  • To Haskell lists
  • Functions
  • Access
  • Update
  • Length
  1. Language Manual
  2. Statements

Mutable Arrays

PreviousReusing existing computationNextCommands

Last updated 2 years ago

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

ArrM Boolean

ArrM (ArrM Field)

ArrM (ArrM Boolean)

Construction / Conversion

From Haskell lists to mutable arrays

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

thaw :: [t] -> Comp (ArrM t)
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.

An array of

An array of

An array of arrays of

An array of arrays of

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

Values
statement
Field elements
Booleans
Field elements
Booleans