# SOLID cairo - The iterator pattern

By [Only Dust](https://paragraph.com/@only-dust) · 2022-05-16

---

When learning a new programming language, you can sometimes feel confused about new paradigms. For me it happened with [cairo](http://cairo-lang.org/) 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](https://mirror.xyz/onlydust.eth/rR2Gt31kGQLlXZ27mLb_4Jtwh-cu8r6v51YSh-ECMw8)

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 :-)

---

*Originally published on [Only Dust](https://paragraph.com/@only-dust/solid-cairo-the-iterator-pattern)*