-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Efficient implementation of lazy monolithic arrays (lazy in indexes).
--
-- This package built on standard array package adds support for lazy
-- monolithic arrays. Such arrays are lazy not only in their values, but
-- in their indexes as well. Read the paper "Efficient Graph Algorithms
-- Using Lazy Monolithic Arrays"
-- (http://citeseer.ist.psu.edu/95126.html) for further details.
@package lazyarray
@version 0.1.1
-- | 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.
module Data.LazyArray.Lowlevel
-- | The lazyarray in construction is not classic Array, but has the
-- same parameters.
data LArray i e
-- | Creates an lazy array, using first argument as 'zero' element for this
-- array. The list of associations is left intact until needed by
-- laAt or laFreeze.
laCreate :: (Ix i) => e -> (i, i) -> [(i, e)] -> LArray i e
-- | 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)
--
laAt :: (Ix i, Eq e) => LArray i e -> i -> e
-- | 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.
laFreeze :: (Ix i, Eq e) => LArray i e -> Array i e
-- | 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)
--
mlaCreate :: (Ix i) => (i, i) -> [(i, e)] -> LArray i (Maybe e)
-- | 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).
--
-- Module Data.LazyArray implements the monolithic lazy array
-- using Array with temporary buffer. For implementation without
-- the temporary buffer see Data.LazyArray.Lowlevel module.
--
-- Don't forget to import some kind of arrays when using this module.
-- Results of small benchmark and a discussion can be found at the bottom
-- of this page.
module Data.LazyArray
-- | This function returns an array, which i-th element is a list, that
-- contains all values associated with i in the list of associations, in
-- that order. In other words, the result of lArray bnds assoc
-- is
--
-- lArray bnds assoc = array bnds [(i,[e|(i',e)<-assoc,i'==i] |
-- i<-range bnds].
--
-- The important difference between the two sides of previous equation is
-- that lArray works in linear time, ie. each member in the
-- assoc list is accessed exactly once, and lArray is
-- lazy in its second argument. It means the assoc list is left
-- intact until an i-th element of the resulting array needs to be
-- evaluated. At that time the assoc list is examined until the
-- first pair (i,e') is found. Until such pair is found, processed
-- elements of assoc are stored at appropriate indexes in the
-- resulting array.
--
-- The implementation uses temporary array for such processed elements of
-- assoc list, that were not yet 'requested' [or 'evaluated'] in
-- the resulting array. This array can be freed when all lists of the
-- resulting array are fully evaluated.
--
-- Here is an example of how to use the monolithic lazy array. Given a
-- graph of type Array Int [Int] we construct the
-- dfs numbering from a given vertex. Obviously, only the first element
-- of the lArray is needed - lArrayFirst,
-- lArrayMaybe or Data.LazyArray.Lowlevel are better choice
-- here.
--
--
-- dnum::Array Int [Int]->Int->Array Int (Maybe Int)
-- dnum g s = amap listToMaybe marks where
-- list = dfs' [s] 0
-- marks = lArray (bounds g) list
-- dfs' [] _ = []
-- dfs' (s:ss) n = (s,n) : if n == head (marks!s) then dfs' ((g!s)++ss) (n+1) else dfs' ss n
--
lArray :: (Ix i) => (i, i) -> [(i, e)] -> Array i [e]
-- | It is often needed to apply some function to the list of elements
-- belonging to the same index. Function lArrayMap is provided,
-- and could be defined like lArrayMap f = (amap f) . lArray.
-- Obviously, lArray = lArrayMap id.
lArrayMap :: (Ix i) => ([e] -> e') -> (i, i) -> [(i, e)] -> Array i e'
-- | This is equivalent to lArrayMaybe = lArrayMap listToMaybe but
-- a bit faster.
lArrayMaybe :: (Ix i) => (i, i) -> [(i, e)] -> Array i (Maybe e)
-- | This is equivalent to lArrayFirst zero = lArrayMap (\x->case x
-- of []->zero; e:_->e) but a bit faster.
lArrayFirst :: (Ix i) => e -> (i, i) -> [(i, e)] -> Array i e