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-Sequence.html
(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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
