Structural recursion for querying ordered graphs

Soichiro Hidaka, Kazuyuki Asada, Zhenjiang Hu, Hiroyuki Kato, Keisuke Nakano

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)


Structural recursion, in the form of, for example, folds on lists and catamorphisms on algebraic data structures including trees, plays an important role in functional programming, by providing a systematic way for constructing and manipulating functional programs. It is, however, a challenge to define structural recursions for graph data structures, the most ubiquitous sort of data in computing. This is because unlike lists and trees, graphs are essentially not inductive and cannot be formalized as an initial algebra in general. In this paper, we borrow from the database community the idea of structural recursion on how to restrict recursions on infinite unordered regular trees so that they preserve the finiteness property and become terminating, which are desirable properties for query languages. We propose a new graph transformation language called λFG for transforming and querying ordered graphs, based on the well-defined bisimulation relation on ordered graphs with special ε-edges. The language λFG is a higher order graph transformation language that extends the simply typed lambda calculus with graph constructors and more powerful structural recursions, which is extended for transformations on the sibling dimension. It not only gives a general framework for manipulating graphs and reasoning about them, but also provides a solution to the open problem of how to define a structural recursion on ordered graphs, with the help of the bisimilarity for ordered graphs with ε-edges.

Original languageEnglish
Title of host publicationICFP 2013 - Proceedings of the 2013 ACM SIGPLAN International Conference on Functional Programming
Number of pages14
Publication statusPublished - 2013
Externally publishedYes
Event2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013 - Boston, MA, United States
Duration: 2013 Sept 252013 Sept 27

Publication series

NameProceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP


Other2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013
Country/TerritoryUnited States
CityBoston, MA


  • Bisimulation
  • Graph query language
  • Optimization
  • Ordered graphs
  • Structural recursion

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Structural recursion for querying ordered graphs'. Together they form a unique fingerprint.

Cite this