Structuring depth-first search algorithms in Haskell

ABSTRACT

Depth-first search is the key to a wide variety of graph algorithms. In this paper we express depth-first search in a lazy functional language, obtaining a linear-time implementation. Unlike traditional imperative presentations, we use the structuring methods of functional languages to construct algorithms from individual reusable components. This style of algorithm construction turns out to be quite amenable to formal proof, which we exemplify through a calculational-style proof of a far from obvious strongly-connected components algorithm.

REFERENCES

• 1: Paul S. Barth , Rishiyur S. Nikhil , Arvind Nikhil, M-structures: extending a parallel, non-strict, functional language with state, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.538-568, June 1991, Cambridge, Massachusetts, United States
• 2: F. Warren Burton , Hsi-Kai Yang, Manipulating multilinked data structures in a pure functional language, Software—Practice & Experience, v.20 n.11, p.1167-1185, Nov. 1990
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: Martin Erwig, Graph Algorithms = Iteration + Data Structures? The Structure of Graph Algorithms and a Corresponding Style of Programming, Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, p.277-292, June 19-20, 1992
• 5: Rachel Harrison, Abstract data types in standard ML, John Wiley & Sons, Inc., New York, NY, 1993
• 6: Ian Holyer, Functional programming with Miranda, Pitman Publishing, London, UK, 1991
• 7: John Hopcroft , Robert Tarjan, Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, v.16 n.6, p.372-378, June 1973 [doi>10.1145/362248.362272]
• 8: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 9: Kashiwagi, Y. and Wise, D. S. (1991), Graph algorithms in a lazy functional programming language, in 'Proceedings of the 4'th International Symposium on Lucid and intensional Programming', pp. 35-46. Also available as Technical Report Number 330, Computer Science Department, Indiana University.
• 10: Launchbury, J. (1993), Lazy imperative programming, in 'Workshop on State in Programming Languages', ACM SIGPLAN, Copenhagen, Denmark, pp. 46-56.
• 11: John Launchbury , Simon L. Peyton Jones, Lazy functional state threads, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.24-35, June 20-24, 1994, Orlando, Florida, United States
• 12: Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 13: E. Moggi, Computational lambda-calculus and monads, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.14-23, June 1989, Pacific Grove, California, United States
• 14: Laurence C. Paulson, ML for the working programmer, Cambridge University Press, New York, NY, 1991
• 15: Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158524]
• 16: Reif, J. H. (1985), 'Depth-first search is inherently sequentiM', Information Processing Letters 20, 229-234.
• 17: Sands, D. (1993), A nai've time analysis and its theory of cost equivalence, TOPPS report D-173, DIKU, University of Copenhagen, Denmark.
• 18: Sharir, M. (1981), 'A strong-connectivity algorithm and its applications in data flow analysis', Computers and mathematics with applications 7(1), 67-72.
• 19: Tarjan, R. E. (1972), 'Depth-first search and linear graph algorithms', SIAM Journal of Computing 1(2), 146- 160.
• 20: Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France [doi>10.1145/91556.91592]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Haskell

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.m Miscellaneous
          Subjects: Reusable software**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Measurement, Verification