On 15 Mar 2021, at 02:11, Daniel Itaborai (via srfi-223 list) <xxxxxx@srfi.schemers.org> wrote:

> In my opinion the API is rather too low level, forcing the user to handle insertion and vector resizing.
>
> Python's list.insert can allocate space for a new element at the end of the list if the indexed position is higher than the last one,
> making the direct use of the bisect functions with list.insert a little bit easier.
> <snip> p.s.:: Were insort_right and insort_left left out as a low hanging fruit to entice new contributors?

The contexts of Scheme and Python are quite different.

Python has one list collection type, a typical dynamically-sized array. Scheme has two: (singly-linked) lists and (fixed-size) vectors.

I must that even in the context of Python I’ve never really understood why it offers a binary search procedure which subsequently does a linear-time insertion into the array. As the documentation, ‘the O(log n) search is dominated by the slow O(n) insertion step’. The only time it can offer amortized O(1) is when the new element is bigger than all the existing ones in the array, and that’s assuming (I’m guessing here) that lists are implemented as typical dynamically-sized arrays underneath with extra empty slots at the end ready for appending. It would make more sense to make a single linear scan over the list which does both searching and inserting. Linear search is out of scope of this SRFI.

For a single linear search-and-insert, Scheme’s list type is more suited than vectors (even flexvectors, imo). When insertions are meant to happen regularly, you should probably be using a balanced binary tree, which actually does give you O(log2 n) insertion time. SRFI 146 seems to be the current relevant spec.

Daphne Preston-Kendal