Abstract
The initial-algebra approach to modelling datatypes consists of giving constructors for building larger objects of that type from smaller ones, and laws identifying different ways of constructing the same object. The recursive decomposition of objects of the datatype leads directly to a recursive pattern of computation on those objects, which is very helpful for both functional and parallel programming.
We show how to model a particular kind of directed acyclic graph using this initial-algebra approach.
This work was partially supported by University of Auckland Research Committee grant numbers A18/XXXXX/62090/3414013, /3414019 and /3414024.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Roland Backhouse. An exploration of the Bird-Meertens formalism. In International Summer School on Constructive Algorithmics, Hollum, Ameland. STOP project, 1989. Also available as Technical Report CS 8810, Department of Computer Science, Groningen University, 1988.
Roland Backhouse, Peter de Bruin, Grant Malcolm, Ed Voermans, and Jaap van der Woude. Relational catamorphisms. In Möller [23], pages 287–318.
R. S. Bird, C. C. Morgan, and J. C. P. Woodcock, editors. LNCS 669: Mathematics of Program Construction. Springer-Verlag, 1993.
Richard S. Bird. Using circular programs to eliminate multiple traversals of data. Acta Informatica, 21:239–250, 1984.
Richard S. Bird. An introduction to the theory of lists. In M. Broy, editor, Logic of Programming and Calculi of Discrete Design, pages 3–42. Springer-Verlag, 1987. Also available as Technical Monograph PRG-56, from the Programming Research Group, Oxford University.
Richard S. Bird. Lectures on constructive functional programming. In Manfred Broy, editor, Constructive Methods in Computer Science. Springer-Verlag, 1988. Also available as Technical Monograph PRG-69, from the Programming Research Group, Oxford University.
Alex Bunkenburg. The Boom hierarchy. In Kevin Hammond and John T. O'Donnell, editors, 1993 Glasgow Workshop on Functional Programming. Springer, 1993.
F. Warren Burton and Hsi-Kai Yang. Manipulating multilinked data structures in a pure functional language. Software—Practice and Experience, 20(11):1167–1185, November 1990.
Virgil Emil Căzănescu and Gheorghe Ştefănescu. Towards a new algebraic foundation of flowchart scheme theory. Fundamenta Informaticae, XIII:171–210, 1990.
Virgil-Emil Căzănescu and Gheorghe Ştefănescu. Classes of finite relations as initial abstract data types I. Discrete Mathematics, 90:233–265, 1991.
Bruno Courcelle. Graph rewriting: An algebraic and logic approach. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, chapter 5. Elsevier, 1990.
Jeremy Gibbons. Algebras for Tree Algorithms. D. Phil. thesis, Programming Research Group, Oxford University, 1991. Available as Technical Monograph PRG-94.
Jeremy Gibbons. Upwards and downwards accumulations on trees. In Bird et al. [3], pages 122–138. A revised version appears in the Proceedings of the Massey Functional Programming Workshop, 1992.
Paul Hoogendijk. Relational programming laws in the Boom hierarchy of types. In Bird et al. [3], pages 163–190.
Johan Jeuring. Deriving algorithms on binary labelled trees. CWI, Amsterdam, July 1989.
Johan Jeuring. The derivation of hierarchies of algorithms on matrices. In Möller [23], pages 9–32.
Yugo Kashiwagi and David S. Wise. Graph algorithms in a lazy functional programming language. Technical Report 330, Department of Computer Science, Indiana University, April 1991.
David J. King and John Launchbury. Lazy depth-first search and linear graph algorithms in Haskell. Department of Computer Science, University of Glasgow, 1993.
Saunders Mac Lane. Categories for the Working Mathematician. Springer-Verlag, 1971.
Lambert Meertens. Algorithmics: Towards programming as a mathematical activity. In J. W. de Bakker, M. Hazewinkel, and J. K. Lenstra, editors, Proc. CWI Symposium on Mathematics and Computer Science, pages 289–334. North-Holland, 1986.
Lambert Meertens. First steps towards the theory of rose trees. CWI, Amsterdam; IFIP Working Group 2.1 working paper 592 ROM-25, 1988.
Paul Molitor. Free net algebras in VLSI-theory. Fundamenta Informaticae, XI:117–142, 1988.
B. Möller, editor. IFIP TC2/WG2.1 Working Conference on Constructing Programs from Specifications. North-Holland, 1991.
Bernard Möller. Derivation of graph and pointer algorithms. In Bernhard Möller, Helmut Partsch, and Steve Schumann, editors, LNCS 755: IFIP TC2/WG2.1 State-of-the-Art Report on Formal Program Development, pages 123–160. Springer-Verlag, 1993.
Bernhard Möller. Algebraic calculation of graph and sorting algorithms. In Dines Bjørner, Manfred Broy, and Igor V. Pottosin, editors, LNCS 735: Formal Methods in Programming and Their Applications, pages 394–413. Springer-Verlag, 1993.
Bernhard Möller and Martin Russling. Shorter paths to graph algorithms. In Bird et al. [3], pages 250–268.
Bob Paige. Comment at IFIP Working Group 2.1 meeting, Renkum, January 1994.
Ross Paterson. Interpretations of term graphs. Draft. Department of Computing, Imperial College, 1994.
David B. Skillicorn. Foundations of Parallel Programming. Cambridge University Press, 1994.
Chris J. Wright. A theory of arrays for program derivation. Transferral dissertation, Programming Research Group, Oxford University, 1988.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gibbons, J. (1995). An initial-algebra approach to directed acyclic graphs. In: Möller, B. (eds) Mathematics of Program Construction. MPC 1995. Lecture Notes in Computer Science, vol 947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60117-1_16
Download citation
DOI: https://doi.org/10.1007/3-540-60117-1_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60117-3
Online ISBN: 978-3-540-49445-4
eBook Packages: Springer Book Archive