Cairo Streams

Array stream library written in pure Cairo

---

⚠️ WARNING! ⚠️

This repo contains highly experimental code. Expect rapid iteration. Use at your own risk.

Installation

If you are using Protostar

protostar install https://github.com/onlydustxyz/cairo-streams

If you are using StarkNet with a Python env or Nile

pip install onlydust-cairo-streams

Usage

To import the library in a cairo file, add this line:

from onlydust.stream.default_implementation import stream

Default implementations

foreach

The foreach() method executes a provided function once for each array element.

Signature:

func foreach(function : codeoffset, array_len : felt, array : felt*)

The provided function must have this signature exactly (including implicit params):

func whatever{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(index : felt, element : felt*)

Example

func test_foreach{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals

    let (local array : felt*) = alloc()
    assert array[0] = 1
    assert array[1] = 1
    assert array[2] = 1
    assert array[3] = 7

    stream.foreach(do_something, 4, array)

    return ()
end

func do_something{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(index : felt, el : felt*):
    ...
    return ()
end

Look here for a full working example.

foreach_struct

The foreach_struct() method executes a provided function once for each array element. Unlike foreach(), the array can be an array of structs.

Signature:

func foreach_struct(function : codeoffset, array_len : felt, array : felt*, element_size : felt)

Assuming the struct is named Foo, the provided function must have this signature exactly (including implicit params):

func whatever{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(index : felt, el : Foo*)

Example

struct Foo:
    member x : felt
    member y : felt
end

func test_foreach_struct{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals

    let (local array : Foo*) = alloc()
    assert array[0] = Foo(1, 10)
    assert array[1] = Foo(1, 10)
    assert array[2] = Foo(2, 20)
    assert array[3] = Foo(7, 70)

    stream.foreach_struct(do_something, 4, array, Foo.SIZE)

    return ()
end

func do_something{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(el : Foo*):
    ...
    return ()
end

Look here for a full working example.

filter

The filter() method executes a "filtering" callback function on each element of the array and keep only the elements that match.

Signature:

func filter(function : codeoffset, array_len : felt, array : felt*) -> (filtered_array_len : felt, filtered_array : felt*)

The callback function must return 0 or 1 and must have this signature exactly (including implicit params):

func whatever{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(el : felt) -> (keep : felt)

Example

func test_filter{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals

    let (local array : felt*) = alloc()
    assert array[0] = 1
    assert array[1] = 2
    assert array[2] = 8
    assert array[3] = 7

    let (local filtered_array_len : felt, filtered_array : felt*) = stream.filter(
        keep_even, 4, array
    )

    assert 2 = filtered_array_len
    assert 2 = filtered_array[0]
    assert 8 = filtered_array[1]

    return ()
end

func keep_even{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(el : felt) -> (
    keep : felt
):
    let (_, rest) = unsigned_div_rem(el, 2)
    return (1 - rest)
end

Look here for a full working example.

filter_struct

The filter_struct() method executes a "filtering" callback function on each element of the array and keep only the elements that match. Unlike filter(), the array can be an array of structs.

Signature:

func filter_struct(function : codeoffset, array_len : felt, array : felt*, element_size : felt) -> (filtered_array_len : felt, filtered_array : felt*)

Assuming the struct is named Foo, the callback function must return 0 or 1 and must have this signature exactly (including implicit params):

func whatever{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(el : Foo*) -> (keep : felt)

Example

struct Foo:
    member x : felt
    member y : felt
end

func test_filter_struct{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals

    let (local array : Foo*) = alloc()
    assert array[0] = Foo(1, 1)
    assert array[1] = Foo(1, 0)
    assert array[2] = Foo(2, 8)
    assert array[3] = Foo(7, 4)

    let (local filtered_array_len : felt, filtered_array : Foo*) = stream.filter_struct(
        keep_even_foo, 4, array, Foo.SIZE
    )

    assert 2 = filtered_array_len
    assert Foo(1, 1) = filtered_array[0]
    assert Foo(2, 8) = filtered_array[1]

    return ()
end

func keep_even_foo{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(
    el : Foo*
) -> (keep : felt):
    tempvar sum = el.x + el.y
    let (_, rest) = unsigned_div_rem(sum, 2)
    return (1 - rest)
end

Look here for a full working example.

map

The map() method executes a "mapping" callback function on each element of the array and store the returned value in-place of the processed element.

Signature:

func map(function : codeoffset, array_len : felt, array : felt*) -> (mapped_array : felt*)

The callback function must have this signature exactly (including implicit params):

func whatever{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(value : felt) -> (result : felt)

Example

func test_map{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals

    let (local array : felt*) = alloc()
    assert array[0] = 1
    assert array[1] = 2
    assert array[2] = 3
    assert array[3] = 4

    let (array) = stream.map(double, 4, array)

    assert 2 = array[0]
    assert 4 = array[1]
    assert 6 = array[2]
    assert 8 = array[3]

    return ()
end

func double{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(value : felt) -> (
    result : felt
):
    return (result=value * 2)
end

Look here for a full working example.

map_struct

The map_struct() method executes a "mapping" callback function on each element of the array and store the returned value in-place of the processed element. Unlike map(), the array can be an array of structs.

Signature:

func map_struct(function : codeoffset, array_len : felt, array : felt*, element_size : felt) -> (mapped_array : felt*)

The callback function must have this signature exactly (including implicit params):

func whatever{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(foo : Foo*) -> (result : Foo*)

Example

struct Foo:
    member x : felt
    member y : felt
end

func test_map_struct{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals

    let (local array : Foo*) = alloc()
    assert array[0] = Foo(1, 10)
    assert array[1] = Foo(2, 20)
    assert array[2] = Foo(3, 30)
    assert array[3] = Foo(4, 40)

    let (local array : Foo*) = stream.map_struct(double_foo, 4, array, Foo.SIZE)

    assert Foo(2, 20) = array[0]
    assert Foo(4, 40) = array[1]
    assert Foo(6, 60) = array[2]
    assert Foo(8, 80) = array[3]

    return ()
end

func double_foo{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(foo : Foo*) -> (
    result : Foo*
):
    return (new Foo(foo.x * 2, foo.y * 2))
end

Look here for a full working example.

reduce

The reduce() method executes a "reducer" callback function on each element of the array.

Signature:

func reduce(function : codeoffset, array_len : felt, array : felt*) -> (res : felt)

The callback function must have this signature exactly (including implicit params):

func whatever{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(initial_value : felt, el : felt) -> (res : felt)

Example

func test_reduce{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals

    let (local array : felt*) = alloc()
    assert array[0] = 1
    assert array[1] = 1
    assert array[2] = 1
    assert array[3] = 7

    let (res) = stream.reduce(sum, 4, array)
    assert res = 10

    # Reading a storage var will fail if builtins haven't been properly updated
    let (dummy) = dumb.read()

    return ()
end

func sum{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(
    initial_value : felt, el : felt
) -> (res : felt):
    let res = initial_value + el
    return (res)
end

Look here for a full working example.

reduce_struct

The reduce_struct() method executes a "reducer" callback function on each element of the array. Unlike reduce(), the array can be an array of structs.

Signature:

func reduce_struct(function : codeoffset, array_len : felt, array : felt*, element_size : felt) -> (res : felt*)

Assuming the struct is named Foo, the callback function must have this signature exactly (including implicit params):

func whatever{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(initial_value : Foo*, element : Foo*) -> (res : Foo*)

Example

struct Foo:
    member x : felt
    member y : felt
end

func test_reduce_struct{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}():
    alloc_locals
    let (local array : Foo*) = alloc()
    assert array[0] = Foo(1, 10)
    assert array[1] = Foo(1, 10)
    assert array[2] = Foo(2, 20)
    assert array[3] = Foo(7, 70)

    let (res : Foo*) = stream.reduce_struct(
        function=sum_foo, array_len=4, array=array, element_size=Foo.SIZE
    )
    assert 11 = res.x
    assert 110 = res.y

    # Reading a storage var will fail if builtins haven't been properly updated
    let (dummy) = dumb.read()

    return ()
end

func sum_foo{syscall_ptr : felt*, pedersen_ptr : HashBuiltin*, range_check_ptr}(
    initial_value : Foo*, element : Foo*
) -> (res : Foo*):
    return (new Foo(initial_value.x + element.x, initial_value.y + element.y))
end

Look here for a full working example.

Custom implementations

You can implement your own functions, with custom implicit arguments, using the generic functions provided by the library:

from onlydust.stream.generic import generic

To see implementation examples, the best is to look at the default implementations.