Skip to main content

An Initial−Algebra Approach to Directed Acyclic Graphs

Jeremy Gibbons

Abstract

The initial-algebra approach to modelling datatypes consists of giving \em constructors\/ for building larger objects of that type from smaller ones, and \em 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. \par We show how to model a particular kind of directed acyclic graph using this initial-algebra approach.

Book Title
Mathematics of Program Construction
Editor
Bernhard Möller
Pages
282–303
Publisher
Springer−Verlag
Series
Lecture Notes in Computer Science
Volume
947
Year
1995