Haskell中的数组越界

roy_hu's picture
Sun, 2008/11/02 - 12:44 — roy_hu

从Haskell Cafe看到的，而且这个bug有一段历史了。不清楚为什么这个问题没人管。
示例代码如下：

import Data.Array

t = listArray ((1,1), (2,2)) [1, 2, 3, 4]

main = print $ t ! (1, 3)

Haskell中没有什么一维数组二维数组的概念，它定义了一个Ix的type class，只要是这个class的instance，都可以作为index。因此我们就可以用一个二元组来实现二维数组。在上面例子中，我们对第一行元素的越界访问被转换到了下一行。

  • Login to post comments
  • 142 reads

Wed, 2008/11/05 - 07:10 — code17

code17's picture

这也不失为一种可能

只要它的语义是 clearly specified 即可，至少这是一种可能性。

我不不熟悉它的库。按照它的这个设计，应该就是类似一位数组加 Index，C 和 Fortran 是不是都是这样的？很久不用记不清了。这种语义至少有两个好处：

  • 快速的 random access。用 array本身不就是为快吗，boundary checking 相当损耗效率。有经验的 OCaml 程序员一般都很少用 get 而是用 unsafe_get。
  • 容易 reshape，n维变m维，无非是改一下 shape info， 作某些 index 计算也很灵活。

但是不知道上面代码的内部表示是什么，如果还是 list，那么意义倒是不大，反正已经很慢了。

Wed, 2008/11/05 - 20:24 — roy_hu

roy_hu's picture

我觉得这个设计还是不好

原因如下：
第一，Haskell既然标榜为类型安全的语言，内存错误是应该避免的。这个例子在我看来属于内存错误。Haskell对“一维数组”有边界检查，对其它Ix类的实例其实也有安全的index函数，但为何弃之不用却使用unsafeIndex，我对其背景不甚了解，似乎与性能有关。
第二，考虑性能也没错，但应该提供两个接口，一个安全，一个不安全，现在只有一个不安全的接口。在没有dependent type的情况下，唯一可靠的方法似乎只能是依赖动态检查。
第三，你要是不想要边界检查，完全可以用unsafeAt

PS：Haskell的数组种类很多，分为immutable/mutable，还有boxed/unboxed之分。具体实现我没有仔细看过，但不是list。

------------分割线----------------------
http://sites.google.com/site/haskell/
http://sites.google.com/site/ocaml/