|Trancón y Widemann, B: Coalgebaic semantics of recursion on circular data structures, CALCO Young Researchers Workshop 2011, 28-42 (2012)|
In functional programming, the combination of recursive functions and circular data is traditionally regarded as ineective, causing vicious circles and hence nontermination. We propose an alternative, coalgebraic perspective that encompasses everything from high-level semantics of data and functions to low-level implementations of evaluation strategies. Under this new perspective, circular data as represented by cycles of pointers among cells in memory can be processed with corecursive functions and predicates realized as search problems. The information required to escape the vicious circles is readily available, assuming a certain style of call-by-value conventions. The basic evaluation techniques, their current implementation and some example applications are described.