3 ms·

What is "open corecursion"?

• tel 12y ago
  Corecursion is when you define the meaning of a type by a coalgebra like x -> F x for some pattern functor F. So, for instance, defining an infinite stream like newtype Stream = Stream { runStream :: (X, Stream) } is corecursion. The interesting part is that whatever defines the stream is forced to fix the Stream type immediately. Open (co)recursion in OO langauges occurs when the recursive type is left undefined (i.e., self is passed in). This allows you to change the type of the object at every step if desired. The similar game in a recursive function might be defining face like so fact :: (Int -> Int) -> (Int -> Int) fact recur n = n * recur (n-1) We "tie the knot" by passing fact to itself fix f = f (fix f) fix fact :: Int -> Int which would allow us to add extra cases as needed let term recur n = if n == 0 then 1 else recur n > fix fact 3 -- infinite loop > fix (term . fact) 3 6 So this is a kind of "mixing" of recursive functions. Open corecursion lets you do OO-like "mixing" of corecursive functions.