Ixの範囲は有限

Problem 169 をやってた時の話。

HaskellのArrayって、よく知らんけど多分なんか複雑な木構造だと思うんですが、単純に連続したメモリ領域なんか確保しないんだろうし、思い切ってインデックスの範囲を ( (0,0), (10^25,84) ) くらい取ってDPしたら Negative range size とかいう例外で落ちました。
要素数が2^31以上になるような範囲は取れないんですね。Ix クラスのメソッド index の型を見てみると、(a,a) -> Int となっている。
Haskellだと普段整数のオーバーフローはあんまり気にしなくて良いし、Integer と Int で型合わないよエラーで静的にチェックできることも多いんですが、この場合Arrayの内部構造に隠れてしまうんで、落し穴っぽいですよね。
まぁHashTable的な使い方しない限りまずそんなでかいArrayは作らないし、それならHashTable使えよっていう気もしますが。2G個のCharの配列ーとかあり得るかな？

ところでこの問題は、フォーラムに5行くらいの超シンプルなHaskellでの解答があって思わず感動しちゃいました。Straightforward DP とか言ってたけど、全然思いつかんかった。