Loading...
Please wait, while we are loading the content...
Similar Documents
Lazy Depth-First Search and Linear Graph Algorithms in Haskell
| Content Provider | Semantic Scholar |
|---|---|
| Author | King, David J. Launchbury, John |
| Copyright Year | 1994 |
| Abstract | Depth-rst search is the key to a wide variety of graph algorithms. In this paper we explore the implementation of depth rst search in a lazy functional language. For the rst time in such languages we obtain a linear-time implementation. But we go further. Unlike traditional imperative presentations, algorithms are constructed from individual components, which may be reused to create new algorithms. Furthermore, the style of program is quite amenable to formal proof, which we exemplify through a calculational-style proof of a strongly-connected components algorithm. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://cs.fit.edu/~ryan/library/functional_programming/king_graph.pdf |
| Alternate Webpage(s) | http://uebb.cs.tu-berlin.de/papers/external/functional-state-guis/linear-dfs.ps.gz |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
