[Haskell-cafe] Structural sharing in haskell data structures?

[Jan-Willem Maessen]

I wanted to clear up one misconception here...

On May 13, 2009, at 12:19 AM, wren ng thornton wrote:

> In heavily GCed languages like Haskell allocation and collection is  
> cheap, so we don't mind too much; but in Java and the like, both  
> allocation and collection are expensive so the idea of cheap  
> throwaway objects is foreign.

Not true!  If you look at the internals of Clojure, you'll discover  
they're using trees with *very* wide fanout (eg fanout-64 leaf trees  
for lists).  Why?  Because it's so cheap to allocate and GC these  
structures!  By using shallow-but-wide trees we reduce the cost of  
indexing and accessing list elements.  I suspect you'd still be hard- 
pressed to support this kind of allocation behavior in any of the  
present Haskell implementations, and Haskell implementations of the  
same kinds of structures have limited fanout to 2-4 elements or so.

Now, if only the Clojure structures supported efficient concatenation...

-Jan-Willem Maessen

>
> -- 
> Live well,
> ~wren
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe