[Haskell-cafe] Re: (flawed?) benchmark : sort

Adrian Hey ahey at iee.org
Mon Mar 10 11:23:51 EDT 2008

Ketil Malde wrote:
> Adrian Hey <ahey at iee.org> writes:
>> But seriously, once you admit the possibility that even if x == y it
>> still matters which of x or y is used in expressions than all hell
>> breaks loose. I shudder to think just how much Haskell code there must
>> be out there that is (at best) ambiguious or just plain "broken" if
>> this is a serious possibility.
> Just search for "copy" (on ByteStrings).
> One program of mine was extracting substrings from a large
> file.  Since the file was pretty huge, I used lazy bytestrings for this
> purpose.  Unfortunately, the short substrings I retained pulled with them
> rather large chunks from the file -- since a bytestring is essentially
> a pointer to a chunk, an offset, and a length.  The solution is
> "copy", which creates a new string, indistinguishable from within
> Haskell, but with very different effects on the program.

We're talking about *semantic correctness*, not efficiency. If you
want to fine tune your code like this you shouldn't be relying
on overloaded general purpose function implementations. E.G. the
COrdering type used by AVL lib is one way to do this. This lets
a combining comparison chose which of two "equal" values is used
(and other things).

Indeed, one of my main objections the having things like biasing
policy as part of a functions specification in that it seriously
inhibits you when producing more refined and efficient implementations.

BTW, I noticed this when I was writing my Data.Map clone. Respecting
the stated biasing policy resulted in less efficient implementations.
It "broke my heart" to knowingly write code that would slow down 99%
of users code just keep the 1% who'd defined broken Ord instances
happy, so I defined biasing policy differently for the clone. On
reflection I think even that was a mistake and is something I intend
drop if I ever do a Hackage release (the lib should not specify
any biasing policy whatsoever).

Adrian Hey

More information about the Haskell-Cafe mailing list