Hostname: page-component-7c8c6479df-5xszh Total loading time: 0 Render date: 2024-03-28T16:46:19.592Z Has data issue: false hasContentIssue false

Efficient graph algorithms using lazy monolithic arrays

Published online by Cambridge University Press:  01 July 1998

THOMAS JOHNSSON
Affiliation:
Department of Computer Science, Chalmers University of Technology, S-412 96 Göteborg, Sweden; (e-mail: johnsson@cs.chalmers.se)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Many, perhaps even most, algorithms that involve data structures are traditionally expressed by incremental updates of the data structures. In functional languages, however, incremental updates are usually both clumsy and inefficient, especially when the data structure is an array.

In functional languages, we instead prefer to express such array algorithms using monolithic arrays – wholesale creation of the final answer – both for succinctness of expression, efficiency (only one array created) and (sometimes) implicit parallelism. The ease with which the solution can be reformulated of course depends on the problem, and varies from trivial (e.g. matrix multiplication), to challenging (e.g. solving linear equation systems using Gauss elimination, which in fact can be done by creating only two arrays, recursively defined, of which one is the answer). Other problems have been notoriously resistant to attack; these usually involve some unpredictable processing order of the elements. One such problem is graph marking, i.e. marking the nodes reachable from a set of roots. Hitherto, no functional method has been known except emulating the traditional imperative solution (King & Launchbury, 1995; Launchbury & Peyton Jones, 1995).

The contribution of 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.

Type
Research Article
Copyright
© 1998 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.