text
text copied to clipboard
A better `Data.Text.Lazy.inits`
#558 made me notice that while the implementation of inits
is overall optimal ( $O(n^2)$ ), it has an awkward property that evaluating the ith text in the result takes $O(i^2)$ time. Ideally this would just take $O(i)$ time, since it involves reaching the ith element in a list and the element is a text of length i.
I believe Data.List.inits
has solved this problem using a queue: https://hackage.haskell.org/package/base-4.19.0.0/docs/src/Data.OldList.html#inits
The same could be adopted here.