[Haskell-cafe] Re: OCaml list sees abysmalLanguage Shootoutresults

[William Lee Irwin III]

At some point in the past, someone's attribution was stripped from:
>> It can't be transparent. A different type for semi-packed strings,

On Fri, Oct 08, 2004 at 07:28:53PM +0100, MR K P SCHUPKE wrote:
> Again I disagree... I dont see why you cannot change the "implementation"
> of lists without changing the "interface"... Good old lists will
> behave like good old lists - just the implementation would try
> and take advantage of blocking of the data wherever possible.

Keith's point regarding sharing is a crucial counterexample to this
proposed transparency.


On Fri, Oct 08, 2004 at 07:28:53PM +0100, MR K P SCHUPKE wrote:
> Perhaps a pragma to change the implementation of lists would ne
> be a sensible way of selecting the implementation. If a clever 
> way of encoding the node-size (for large cells) is used, then 
> it would be no slower than normal list code... One way of doing this
> would be to only change the format of cells where the next link is
> null (IE the end of the list)... In this case normal cells would
> be encoded _exactly_ as they are at the moment (so no slowdown
> or increase in memory usage) - to encode a large cell, the next
> pointer is null, and then an extra data structure determines
> if this really is the end of the list, or if infact it is a large
> cell (so we need an item count, and a _real_ next cell link,
> plus the data block)

I'd be fine with an alternative data type supporting e.g. packing and
perhaps O(lg(n)) (!!) and (++) (if I get my wishes wrt. choices of
data structures to implement it). The packing semantics are the crucial
bit that probably makes this awkward to do in idiomatic Haskell, but
there are probably low-level GHC extensions or possibly even
standardized low-level operations I'm not aware of that make such
feasible to implement as just a Haskell library. Someone more cognizant
of those things should probably chime in here for my benefit, as my
interest in this is such that I'd be willing to, say, write my own.


-- wli