[Haskell-cafe] Purely funcional LU decomposition

[wren ng thornton]

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