[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[1] is often known as "difference lists", which the estimable 
Don Stewart has already packaged up for us:



[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,

More information about the Haskell-Cafe mailing list