Requirements for collections extensions

[mark-koch]

The current Collections extension is mostly a placeholder and only defines two ops. Below are some list ops that are required for Guppy:

• Pop: List(T) -> T, List(T) or List(T) -> Sum((T, List), Error)
• Push: T, List(T) -> List(T)
• Length: List(T) -> int or List(T) -> int, List(T)?
• Non-linear indexing: List(T), int -> T or List(T), int -> T, List(T) but the element is not removed from the list!

Nice to have ops (but could also be implemented by hand):

• New list from elements: T, T, ... -> List(T)
• Pop at index: List(T), int -> T, List(T)
• Is empty: List(T) -> Bool
• Is nonempty: List(T) -> Bool
• Append: List(T), List(T) -> List(T)
• Repeat: (List(T), Int) -> List(T) for copyable T
• Find: (List(T), T) -> Int for equatable T
• Count: (List(T), T) -> Int for equatable T
• Map: (S -> T), List(S) -> List(T)
• Filter: (T -> Bool), List(T) -> List(T)
• FilterMap: (S -> Bool), (S -> T), List(S) -> List(T)
• Zip: List(S), List(T) -> List(Tuple(S, T))
• Reverse: List(T) -> List(T)
• Sort: (T, T -> Bool), List(T) -> List(T)
• Contains: List(T), T -> Bool for equatable T

At the moment, we only target immutable classical lists for Guppy. However, later we might also want updating at a given index: List(T), int, T -> List(T).

Would it make sense to add a notion of immutable list to Hugr? The Hugr runtime wouldn't need to copy these lists if a port is connected multiple times.

Generally, some of the functions above only make sense for non-linear lists (e.g. Filter). Do we want to offer different APIs depending on linearity?

[mark-koch]

Decisions

Results from a meeting with @ss2165 and @doug-q

Core collections extension

The core collections extension will contain the following ops:

• Pop: List(T) -> Sum(T, ()): Removes an element at the end of a list. The unit return is for the empty list.
• Push: List(T), T -> List(T): Appends an element at the end of a list.
• Length: List(T) -> List(T), int64: Returns the length of a list.
• Lookup: List(T), int64 -> Sum(T, ()) for copyable T: Returns a copy of the element at a given index.
• Insert: T, int, List(T) -> List(T): Adds an element to a list at a given index
• Map: (S -> T), List(S) -> List(T): Applies a function on every element of a list
• MakeList: T, T, ... -> List(T): Creates a list from elements. Uses varargs similar to the MakeTuple op. The type T should be specified as a parameter for the op.

Considered but rejected for now

• IsEmpty: List(T) -> Sum(List(T), ()). If the list is not empty, the list is returned back so that it can be used again. If the list is empty, it can be safely discarded and we only get unit back. Unfortunately, the Guppy type system cannot capture this return type yet, so we opted for keeping it out of the extension for simplicity for now.

Guppy extension

Furthermore, we will define a custom Guppy extension for special collection ops that are required by Guppy. This extension will live in the Guppy repo. Some of these ops might also be replaced with a Guppy implementation in the future.

• Pop: List(T) -> T: Removes an element at the end of a list and panics if the list is empty
• Length: List(T) -> int64 for copyable T: Returns the length of a classical list
• PopIdx: List(T), int64 -> T, List(T) Removes the element at a given index from a list and returns it. Panics if the index is out of bounds.
• Lookup: List(T), int64 -> T for copyable T: Returns a copy of the element at a given index. Panics if the index is out of bounds.
• IsNonEmpty: List(T) -> Bool, List(T): Checks if a list is empty
• Concat: List(T), List(T) -> List(T): Concatenation of two lists
• Repeat: List(T), Int -> List(T) for copyable T: Returns multiple copies of a list concatenated together
• Filter: (T -> Bool), List(T) -> List(T)
• Reverse: List(T) -> List(T)

Unclear

Some list operations require that the element type is equatable or sortable. It would be nice if the corresponding hugr ops could take an equality or ordering predicate as an argument. However, following the proposed changes in #285 (comment) it would become impossible to use polymorphicly defined functions in this context. Until this question is resolved, we delay making a decision on the following ops:

• Find
• Count
• Contains
• Sort