Efficient Graph Algorithms Using Lazy Monolithic Arrays

this paper is to show how this problem, and some related ones, can be solved using a novel array creation primitive, lazier than previous ones. Thus, in section 2 we specify the array creation primitive lazyArray. In section 3 we give the solution to the graph marking and depth-first numbering problems using our lazy arrays. In section 4 we show how a related and more general problem, that of computing the transitive closure of a binary relation, can be solved in a similar manner. Graph based unification is an essential ingredient in a time and space efficient type inferencer: in section 5 we give such an algorithm in the same style. In section 6 we show how lazy arrays can be implemented efficiently with low-level graph reduction code. In section 7 we discuss space efficiency. Programs in this paper will be given in the nonstrict purely functional language Haskell. 2 Lazy Array