Introduction
Arrays
The Cairo core library implements an Array type.
It is similar to the usual array types found in other programming languages, but with a few key differences:
- Elements can be efficiently added only to the back of the
Array type, and they can only be efficiently removed from the front.
- It is impossible to manually set an item using the array index.
Arrays can be created using the ArrayTrait::new function and also the array! macro:
let empty: Array<u32> = ArrayTrait::new();
let one_to_four = array![1, 2, 3, 4];
Elements can be added to the array using the ArrayTrait::append function:
let mut num_array = array![1, 2, 3, 4];
num_array.append(5);
// -> [1, 2, 3, 4, 5]
Elements can be removed from the array using the ArrayTrait::pop_front function:
let mut one_to_four = array![1, 2, 3, 4];
one_to_four.pop_front();
// -> [2, 3, 4]
Cairo also introduces a Span type that acts like a "snapshot" of the Array.
Every Array can be converted into a Span with the ToSpanTrait::span function:
let one_to_four = array![1, 2, 3, 4];
let one_to_four_span = one_to_four.span();
// -> [1, 2, 3, 4]
Converting an array into a Span is very efficient, as Span is just a data structure that allows Cairo to "view" a section of the array, it doesn't modify it in any way.
By converting an array into a Span, Cairo allows more operations to be performed than would be permitted on Array directly, like removing an item from the front of the span.
let one_to_four = array![1, 2, 3, 4];
let mut one_to_four_span = one_to_four.span();
one_to_four_span.pop_back();
// -> [2, 3, 4]
Note that we had to make one_to_four_span mutable with the mut keyword in order to invoke pop_back, which mutates the span by shortening the section of the array the span is "viewing".
Instructions
As a magician-to-be, Elyse needs to practice some basics.
She has a stack of cards that she wants to manipulate.
To make things a bit easier she only uses the cards 1 to 10.
The stack of cards is represented by an Array, with the bottom of the stack at the front of the array, and the top of the stack at the back.
1. Insert a card at the of top the stack
Implement the function insert_top that returns a copy of the stack with the new card provided added to the top of the stack.
let stack = array![5, 9, 7, 1];
insert_top(stack, 8);
// -> [5, 9, 7, 1, 8]
2. Remove the top card from the stack
Implement the function remove_top_card that returns a copy of the stack having had its top card removed.
If the given stack is empty, the original stack should be returned, unchanged.
let stack = array![3, 2, 6, 4, 8];
remove_top_card(stack);
// -> [3, 2, 6, 4]
3. Insert a card at the bottom of the stack
Implement the function insert_bottom that returns a copy of the stack with the new card provided added to the bottom of the stack.
let stack = array![5, 9, 7, 1];
insert_bottom(stack, 8);
// -> [8, 5, 9, 7, 1]
4. Remove a card from the bottom of the stack
Implement the function remove_bottom_card that returns a copy of the stack having had its bottom card removed.
If the given stack is empty, the original stack should be returned, unchanged.
let stack = array![8, 5, 9, 7, 1];
remove_bottom_card(stack);
// -> [5, 9, 7, 1]
5. Check size of the stack
Implement the function check_size_of_stack that checks whether the size of the stack is equal to a given stack_size or not.
let stack = array![3, 2, 6, 4, 8];
check_size_of_stack(stack, 4);
// -> false
To understand why working with arrays in Cairo is not as straightforward as in other programming languages, it is helpful to bear in mind that Cairo uses an immutable memory model, meaning that once a memory cell is written to, it can't ever be overwritten, only read from.
The language abstracts away this feature somewhat, allowing developers to declare and use their variables as if they were mutable.
Although this makes writing code a bit more challenging, especially code that makes use of the Array type (including ByteArray, which underneath is an "array of bytes"), it enables writing provable programs which can be confidently executed even on untrusted machines, making the trade-off more than worth it.
Learning Exercise
