[Haskell-cafe] Error in array index.

wren ng thornton wren at freegeek.org
Thu Jun 25 00:02:07 EDT 2009

Jason Dusek wrote:
>   Why is `Int` used in so many places where it is
>   semantically wrong? Not just here but also in list indexing...
>   Indices/offsets can only be positive and I can't see any good
>   reason to waste half the address space -- yet we encounter
>   this problem over and over again.

I think history is the biggest culprit. Haskell98 doesn't ship with Nat 
and Natural types, so Int and Integer are used instead. And then the 
Word* types come around for bit bashing.

Another big culprit is that this is one of the places where Haskell 
gives a nod to performance. Many Prelude functions like take, drop, and 
(!!) should accept any Natural. Failing that, they should accept Integer 
and do the right thing for negatives. But most of the time an Int is 
sufficient, and that's what they take; this increases CPU performance, 
but more importantly it increases programmer performance since they 
don't need to write All Those Conversion Functions(tm). Though 
programmer performance suffers when an unbounded type is actually 
required, or when negatives aren't handled correctly.

The haskell' committee is considering adding a Nat or Natural type, so 
history may eventually be corrected. However, in order to deal with them 
in an, er, natural way the numeric typeclass hierarchy needs fixing. At 
the very least we'd want to separate (+) and (*) from (-), negate, abs, 
and signum so that we have a class for Nat and Natural that doesn't have 
partial functions. A safe version of (-) would be nice, though it's an 
open question whether x-(x+y) should be 0 or Nothing[1]. It's also 
unclear what should happen to fromInteger: do we have fromNatural be a 
subfunction of it, or do we desugar negative literals with negate and 
fromNatural and drop fromInteger entirely?

[1] My vote would be for Nothing so that we don't loose the information 
about whether the two operands are equal. Though this has the 
unfortunate side effect of requiring more plumbing. We could always 
offer both variants, so that clients who use subtraction and equality 
comparisons together frequently can use the Maybe version and those who 
want the other mathematical function can use it instead.

Live well,

More information about the Haskell-Cafe mailing list