[Haskell-cafe] Purely funcional LU decomposition
wren ng thornton
wren at freegeek.org
Thu Feb 5 20:46:00 EST 2009
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))):
(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 is often known as "difference lists", which the estimable
Don Stewart has already packaged up for us:
 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 (++).
More information about the Haskell-Cafe