Representing cyclic structures as nested datatypes

Tarmo Uustalu

Institute of Cybernetics

Thursday, 16 March 2006, 14:00
Cybernetica Bldg (Akadeemia tee 21), room B101

Slides from the talk [pdf]

Abstract: We show that cyclic structures, i.e., finite or possibly infinite structures with back-pointers, unwindable into possibly infinite structures, can be elegantly represented as nested datatypes. This representation is free of the various deficiencies characterizing the more naive representation as mixed-variant datatypes. It is inspired by the representation of lambda-terms as a nested datatype via the de Bruijn notation. (Joint work with Neil Ghani, Makoto Hamana, Varmo Vene.)

Tarmo Uustalu
Last update 23.3.2006