text icon indicating copy to clipboard operation
text copied to clipboard

A better `Data.Text.Lazy.inits`

Open meooow25 opened this issue 4 months ago • 4 comments

#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.

meooow25 avatar Feb 16 '24 20:02 meooow25