笔记accumArray

累加数组

:: Ix i
=> (e -> a -> e)  --累加函数, 初始值(列表中的值)和累加值可以是不同类型
-> e             	            --初始值
-> (i, i)	           --数组的边界
-> [(i, a)]	         --被处理的关联列表,(坐标, 值)
-> Array i e

[pearls]第一章用到的checklist就是用accumArray实现的.
checklist用来记录一组数据中出现了指定范围内的哪些数字. 比如检查某list中在区间[2,5]之间的有哪些元素.

checklist :: [Int] -> Array Int Bool

--函数 把一组输入转化成坐标为Int, 值为Bool的表.
用checklist检查一组数中不存在的最小的自然数(含0), 比如[0,1,2,4,5] 不存在的最小数就是3

checklist xs = accumArray (||) False (0, n) (zip (filter (<= n) xs) (repeat True))
where n = length xs

另一个效率更高的数据结构是Data.Array.ST 不过这个不是pure的.