I’ve been looking at
and I couldn’t find a function to insert an element in a list at position i.
I’m a bit surprised because there seem to be a lot of functions in these two modules, that I guess would be used less frequently than inserting an element at the i-th position.
I could write this function myself, but I was thinking maybe it’s already in there and I didn’t see it.
That surprises me as well that there isn’t a
List.Extra.insert. That said, it’s not too hard to implement
insert i value list = List.take i list ++ [ value ] ++ List.drop i list
It’s probably not available because it looks efficient but actually isn’t. You would have the same runtime bound by converting to an array, doing the insert, and then converting back to a list. If you find you need to insert at arbitrary positions, you should consider using an array instead of a list the whole time.
Using an array is not practical at all, and this isn’t more efficient.
Suppose I have an array that looks like this
“a”, “b”, “c”, “d”, “e”
Suppose I want to insert “X” at the position 2 in the array to obtain
“a”, “b”, “X”, “c”, “d”, “e”
You can’t do this with better than linear time with an array. Not even considering the fact that you have to grow the array, these “c”, “d”, “e” values have to be copied to their new positions.
You can, because
Array.append are log time not linear. Of course, you will only see a difference for large enough arrays.
Check out this example of a gap buffer capable of working smoothly with 1M lines of text, implemented using arrays and making use of
Array.append to quickly insert or refocus the ‘gap’:
Ok, I thought Array was a simple array, but apparently it’s more high tech than that. I just read about RRB trees.
Then there should be an insertAt function in the Array type!
Thanks everybody for your replies.
There is! It’s in the elm-community/array-extra package.
Amazing. Thanks dta.
This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.