When learning a new programming language, you can sometimes feel confused about new paradigms. For me it happened with cairo and its lack of for loops.

Indeed, as the memory is immutable in cairo, the usage of iterators is not possible. Only recursion remains.

To illustrate this article, let’s assume we have a grid structure (with a width and height) and that each cell can be accessed using its (x,y) coordinates.

We will use the OOP-like pattern described here

Let’s see how it looks:

# grid.cairo
%lang starknet

from starkware.cairo.common.alloc import alloc

struct Grid:
    member width : felt
    member height : felt
    member cells : felt*
end

# External functions
namespace external:
    func create(width : felt, height : felt) -> (grid : Grid):
        let (cells) = alloc
        return (grid=Grid(width, height, cells))
    end

    func get_cell_at{grid : Grid}(x : felt, y : felt) -> (cell : felt):
        let (index) = internal.index_of(x, y)
        return (cell=grid.cells[index])
    end

    func set_cell_at{grid : Grid}(x : felt, y : felt, cell : felt):
        let (index) = internal.index_of(x, y)
        assert grid.cells[index] = cell
        return (cell=grid.cells[index])
    end
end

# Internal functions
namespace internal:
    func index_of{grid : Grid}(x : felt, y : felt) -> (index : felt):
        return (index=grid)
    end
end

Letting aside the grid filling for the moment, let’s focus on how to iterate over the grid in an external contract. In a naive implementation, it would look like this:

# main.cairo
%lang starknet

from src.grid import Grid, external as grid_access

func new_filled_grid(width : felt, height : felt, value : felt) -> (grid : Grid):
    alloc_locals

    let (local grid) = grid_access.create(width, height)
    fill_grid_loop(grid, 0, 0, value)
    return (grid=grid)
end

func fill_grid_loop(grid : Grid, x : felt, y : felt, value : felt):
    if y == grid.height:
        return ()
    end

    if x == grid.width:
        return fill_grid_loop(grid, 0, y + 1, value)
    end

    with grid:
        grid_access.set_cell_at(x, y, value)
    end

    return fill_grid_loop(grid, x + 1, y, value)
end

There are several drawbacks with this approach, but the main one is that the main contract knows too much about the internal structure of the grid.

The grid should be responsible of its own structure. It should know how to iterate through it. But there is no foreach -like function in cairo. So what can we do ?

Well, we can implement the Iterator design pattern.

This pattern requires to define:

• An iterator structure to hold the progress
• A start() function to return the first cell of the grid
• A next() function to return the next cell of the grid
• A done function to return true when the loop is over

Here is how it looks:

# grid.cairo
%lang starknet

from starkware.cairo.common.alloc import alloc

struct Grid:
    member width : felt
    member height : felt
    member cells : felt*
end

struct Iterator:
    member x : felt
    member y : felt
end

# External functions
namespace external:
    func create(width : felt, height : felt) -> (grid : Grid):
        let (cells) = alloc()
        return (grid=Grid(width, height, cells))
    end

    func get_current_cell{grid : Grid, iterator : Iterator}() -> (cell : felt):
        let (index) = internal.index_of(iterator.x, iterator.y)
        return (cell=grid.cells[index])
    end

    func set_current_cell{grid : Grid, iterator : Iterator}(cell : felt):
        let (index) = internal.index_of(iterator.x, iterator.y)
        assert grid.cells[index] = cell
        return ()
    end

    func start{grid : Grid}() -> (iterator : Iterator):
        return (iterator=Iterator(0, 0))
    end

    func next{grid : Grid, iterator : Iterator}() -> ():
        if iterator.x == grid.width - 1:
            let iterator = Iterator(0, iterator.y + 1)
            return ()
        end

        let iterator = Iterator(iterator.x + 1, iterator.y)
        return ()
    end

    func done{grid : Grid, iterator : Iterator}() -> (is_done : felt):
        if iterator.y == grid.height:
            return (is_done=1)
        end
        return (is_done=0)
    end
end

# Internal functions
namespace internal:
    func index_of{grid : Grid}(x : felt, y : felt) -> (index : felt):
        return (index=y * grid.width + x)
    end
end

And here is how to use it:

# main.cairo
%lang starknet

from src.grid import Grid, Iterator, external as grid_access

func new_filled_grid(width : felt, height : felt, value : felt) -> (grid : Grid):
    alloc_locals

    let (local grid) = grid_access.create(width, height)
    with grid:
        let (iterator) = grid_access.start()
        with iterator:
            fill_grid_loop(value)
        end
    end
    return (grid=grid)
end

func fill_grid_loop{grid : Grid, iterator : Iterator}(value : felt):
    let (is_done) = grid_access.done()
    if is_done == 1:
        return ()
    end

    grid_access.set_current_cell(value)
    grid_access.next()

    return fill_grid_loop(value)
end

Note: It is possible to improve this code by modifying the iterator struct to be only a felt, as the main contract does not need to know the structure of the iterator anymore !

Using this pattern, we could also implement easily other kind of operators like the reverse iterator. But I will let this as an exercise :-)