Editing Talk:Corecursion (section)

== Related concepts? ==

I’d be interested in related concepts for context and to help people more familiar with other areas. Notably, in set theory/logic terms, recursion/corecursion sound similar to the [[recursive set]]/[[recursively enumerable set]], in the the former is “defined by input” while the later is “defined by output” – corecursion and recursively enumerable both sound basically like “what you can get as output”.

Corecursion also feels ''very'' similar to [[tail recursion]], or perhaps better, a generalization – more precisely, tail recursion feels like doing recursion by having a ''backwards'' corecursion; the accumulator variable you often find in tail recursions in the give-away (the accumulator is the corecursive sequence). For example, computing the factorial via tail recursion actually consists of computing the [[falling factorial]] corecursively, and then outputting the end of this sequence (which is finite if you start at a natural number). Indeed, user [http://stackoverflow.com/users/849891/will-ness Will Ness] at StackOverflow claims that corecursion is basically (exactly?) [[tail recursion modulo cons]] (e.g., [http://stackoverflow.com/a/10874351 this answer], July 2012). As intriguing as this may seem, I didn’t find any substantiation of this in a quick literature/Google search, so this may be completely mistaken, and in any case is unsourced speculation.

If anyone could find discussions of corecursion that are not just in abstract functional programming terms, they would be quite appreciated!
:—Nils von Barth ([[User:Nbarth|nbarth]]) ([[User talk:Nbarth|talk]]) 18:30, 25 July 2012 (UTC)

: Some related concepts:
:* Codata (or coinductive types) are defined by [[coinduction]], that is as the [[greatest fixpoint]] of a set of equations. These types can model infinite structures (e.g. potentially infinite lists or [[stream (type theory)|stream]]s). In strict languages you have to do explicit [[lazy evaluation]] to work by those types, e.g. explicit delaying and forcing, or using generators. 
:* Regular data is defined inductively, that is as the [[least fixpoint]] of a set of equations. These types can only model finite structures (e.g. finite lists).
: I don't immediately see the connection with tail recursion modulo cons. Perhaps it's related to guarded recursion? —''[[User:Ruud Koot|Ruud]]'' 19:32, 25 July 2012 (UTC)