This is an implementation of monolithic lazy array. If you want to know what an monolithic lazy array is good for, you can read for example the paper "Efficient Graph Algorithms Using Lazy Monolithic Arrays": http://citeseer.ist.psu.edu/95126.html.

This module implements lowlevel lazy array somewhat similar to Data.LazyArray.lArrayFirst, so read its description first. This implementation uses no temporary buffer (at least in optimised GHC build) and for index i it returns not the first associated element, but the first 'nonzero' element (or 'zero' if there are no elements). Don't forget to import some kind of arrays when using this module.

Benchmark of various implementations of DFS can be found in the Data.LazyArray module.

This specialised lazy array is not an Array when being constructed, but can be converted to (using Data.Array.MArray.unsafeFreeze) when fully built. The usage of Data.Array.MArray.unsafeFreeze is safe and when using optimised build, it is inplace and imposes no overhead.

The usage is very similar to Data.LazyArray, which is demonstrated on the example from that module:

dnum::Array Int [Int]->Int->Array Int Int
dnum g s = laFreeze marks where
   list = dfs' [s] 0
   marks = laCreate (-1) (bounds g) list
   dfs' []     _ = []
   dfs' (s:ss) n = (s,n) : if n == (marks `laAt` s) then dfs' ((g!s)++ss) (n+1) else dfs' ss n

Returns an element on the i-th position of the lazy array. If it was already found, just return it. If it was not found yet, consume the list of associations until it is empty or the 'nonzero' association for i is found. If no 'nonzero' association is found, returns 'zero'. All visited elements from the association list are processed and not visited any more.

When not concerned about the laziness and time complexity,

(laCreate zero bnds assoc) `laAt` i = zero `fromMaybe` (find (\(i',e)->i'==i && e/=zero) assoc)

Convert lazy array to Array. Because the result is not lazy, this function forces the evaluation of the whole association list before returning, so it should be used when the lazy array is fully contructed (ie. the association list is ended by []).

Once again - this function is really "non-lazy", as it traverses the whole associtation list, no matter which elements from the resulting Array will be needed. Even if only 1-st element is needed and even if it could already be found, the whole rest of the association list is processed. (Small heuristic is implemented - when all members of resulting Array are 'nonzero', the traversal of the association list is stopped.)

This function uses Data.Array.MArray.unsafeFreeze to convert IOArray to Array. It is used after the whole association list is processed, so it is safe, and when using optimised GHC build, it imposes no time or space overhead.

This method creates lazy array using Nothing for 'zero' element. It is just a simple wrapper of laCreate:

mlaCreate bnds assoc = laCreate Nothing bnds (map (\(i,e)->(i,Just e)) assoc)