Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: