Rafael Gustavo da Cunha Pereira Pinto wrote:
What I miss most is a data structure with O(1) (amortized) direct access.
Finger trees get close, O(log(min(i,n-i))): http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-... (And Theta(1) amortized for all dequeue operations to boot.)
One of the changes I thought today was to remove the ++ operator and create a list of lists that I would concat in the last call.
Don't do it manually, let an abstract type do the optimization for you. This idea[1] is often known as "difference lists", which the estimable Don Stewart has already packaged up for us: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist :) [1] Actually, not quite that idea. The idea instead is to represent a list as a function [a]->[a] and then compose these functions (rather than concatenating the strings). At the very end once you're done, pass in [] and get back the whole list in O(n) time, rather than the O(n^2) that commonly arises from using (++). -- Live well, ~wren