Corecursion

[Pitarou]

This is the missing piece from my mental toolbox. I wish I'd known about it years ago.

Co-recursion is a principled way to turn a top-down algorithm into a bottom-up one. For instance, in Haskell, it's easy to write the fibonacci series from its definition:

    fibonacci 0 = 1
    fibonacci 1 = 1
    fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

But this is ridiculously inefficient. Until now, the only "principled" way I knew of to transform this into something sensible was through memoization, but that's still very wasteful.

With co-recursion in my toolkit, I can transform this into a form that generates the whole series as a stream:

    fibonacci_series = 0: 1: more fibonacci_series
      where
        more f1: rest@(f2: _) = f1 + f2: more(rest)

And thanks to Haskell's lazy, garbage collected semantics, taking the nth element of the series (remembering to drop data I don't need) turns out to be equivalent to:

    fibonacci n = fib n 0 1
      where
        fib 0 a b = a
        fib n a b = fib (n-1) b (a+b)

Which is what we wanted. :-)

[jgg]

Corecursion is useful for taking a recursive algorithm and transforming it to a stream-like output pattern.

But this is ridiculously inefficient.

Well...you might be surprised in the general case. Because of lazy evaluation, Haskell won't necessarily implode on non-TCO recursive functions (example: http://stackoverflow.com/questions/13042353/does-haskell-hav...), and will actually sometimes cause a stack overflow on "optimized" functions.

Until now, the only "principled" way I knew of to transform this into something sensible was through memoization, but that's still very wasteful.

I think "real" Haskell code usually favors operations of lists over recursive functions. That said, the standard way to transform your recursive structure into something "sensible" is to use a tail-recursive function. In basically any other functional language, you'd go with that approach.

To get the same "benefit" in Haskell, you'd have to force strict evaluation inside of a tail-recursive function. This prevents a thunk from causing problems. That said, Haskell doesn't always build up a normal stack on a regular recursive call.

Otherwise, you'd just use a list structure.

(Someone correct me if I've said something stupid.)

ref:

http://www.haskell.org/haskellwiki/Tail_recursion

[gamegoblin]

Alternatively, making use of laziness and recursive definitions:

  fibonacci n = fibs !! n
  fibs = 1:1:zipWith (+) fibs (tail fibs)

[shoki]

Not corecursive, but here's the SICP O(ln(n)) algorithm:

    fibonacci = fib 1 0 0 1
      where
        fib a b p q n
          | n == 0 = b
          | even n = fib a b p' q' (n `div` 2)
          | otherwise = fib a' b' p q (n - 1)
            where
              p' = p*p + q*q
              q' = 2*p*q + q*q
              a' = a*q + b*q + a*p
              b' = b*p + a*q

[Osmium]

> But this is ridiculously inefficient.

I'm sorry, but I don't understand this. How is that inefficient?

[wyager]

Alternatively,

     fibonacci n = (map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)) !! n

[LBarret]

did you read SICP (this is explained in the first chapters of the book) ? if not you're for a treat.

[gamegoblin]

Some places I find myself using corecursion:

Minimax algorithm: https://en.wikipedia.org/wiki/Minimax (I actually generally use negamax, the non-corecursive version, but you should understand minimax first)

"Tying the knot" in Haskell

That is, it's possible to create circular lists in Haskell like so:

    let x = 1:y    -- x = 1 cons y
        y = 0:x    -- y = 0 cons x
    in x           -- return x

Which will return an infinite list of alternating 1's and 0's which only take up 2 ints (and pointers) worth of memory. Calling the millionth index merely runs in circles around the list until it's followed a million pointers.

EDIT: Minimax is mutual recursion, not corecursion, whoops.

[zwegner]

> Minimax algorithm: https://en.wikipedia.org/wiki/Minimax (I actually generally use negamax, the non-corecursive version, but you should understand minimax first)

That's mutual recursion, not corecursion. Check the article out, corecursion has a much more... "mathematical" definition, relating to the types of initial data and final data.

By my quick reading, your second example might be considered corecursion (but I think is also just regular recursion). It might not be considered recursion at all, in this particular sense, as it's only one piece of infinite data, not a function that takes an input. I'm not the best algebraist though.

[XaspR8d]

Dang it. Every time I see something like this, I really get excited for this summer when I have time blocked off for learning Haskell.

[tel]

Basically any unfold is corecursive.

[Dn_Ab]

Analogies are lossy but one way to think of corecursion/recursion is that corecursion turns the seed into a maple tree and recursion eats the tree's branches and spits out a table leg or something. Corecursion is generative and (structural) recursion aggregates/builds. You corecursively generate a possibly infinite stream while you recursively turn a finite list of numbers into their sum.

Other places you've probably already seen corecursiveness: Power Series in calculus, automatons in computer science and in the close cousin that is the so called map in MapReduce TM.

Programming with just (primitive but on higher order functions) recursion and corecursion is the basis of Total Functional Programming which, while not Turing complete is still very surprisingly powerful.

[oggy]

What are the restrictions on combining primitive recursive and co-recursive functions in total functional programming? Clearly, "repeat" is primitively co-recursive, and "length" is primitively recursive, but "length . repeat" is non-terminating.

[crashandburn4]

Am I misunderstanding this? reading all the examples, the difference between recursion and corecursion seems to be equivalent to the difference between tail recursion and stack recursion. Is that right?

can anyone post an example of corecursion that is stack recursion? or is there something else that needs to happen to qualify something as corecursion?

[tel]

Those are just at different levels of meaning. I don't think there's a direct relationship between stack/tail recursion and recursion/corecursion.

To get a brief feel for the difference consider the "type function":

    T x = 1 + x

where 1 is the type with only one value and the type (X + Y) is the tagged union of types X and Y. We might decide to talk about the type "iterated T" as the type

    IT = T (T (T (T (T (T ...))))))
       = 1 + (1 + (1 + (1 + (1 + ...))))))

If we tag "left" values with Inl and "right" values with Inr and take * to be the only value of type 1, then values of IT look like

    Inl *
    Inr (Inl *)
    Inr (Inr (Inr (Inr (Inl *))))

which looks a lot like the Peano Naturals. Now, a recursive definition on IT looks like

    cata : forall x . (T x -> x) -> IT -> x

and a corecursive definition looks like

    ana : forall x . (x -> T x) -> x -> IT

In other words, recursion occurs by constantly pulling "layers" of type T off of values of IT while corecursion occurs by adding "layers" of type T on to seed values to build an IT.

We can convert IT to natural numbers by using cata

    cata (\tx -> case tx of { Inr * -> 0; Inl n -> 1 + n })

and we can invert that conversion with ana

    ana (\x -> case (x > 0) of { True -> Inl x; False -> Inr * })

and we can build the "infinite" structure omega with ana

    omega = ana (\x -> Inl x)

[ww520]

They are different animals. Stack recursion/heap-based recursion or tail recursion are mechanism to implement recursion. Recursion and co-recursion are the usage of recursion with different way to manage the input data.

Recursion tends to just process the input data one by one until there's no more. Co-recursion would add more to the input data along the way.

Let's say I have a list of numbers. In each step of the recursion, a number is removed. If the number is odd, it's dropped. If the number is even, a randomly generated set of numbers is added to the input list, adding more to it. The recursion would take longer. Hopefully it will end if there's no more even number.

[Sharlin]

I believe the following is a corecursive analog for a stack recursive factorial implementation in Python:

    def factorial(i = 1):
        yield i
        for j in factorial(i + 1):
            yield j*i

Not sure why anyone would want to implement it like that, though.

[Dewie]

I guess an example of corecursion is an inductive definition of the natural numbers:

Let N be a set.

1. zero is in N.

2. If an element e is in N, then s(e) is in N.

You get: {zero, s(zero), s(s(zero)),...} (of course in any order, since sets are unordered).

You start from zero and build the whole infinite set from that starting point. Bottom up.

[adamnemecek]

I posted this since I didn't know it had a name.

[coolsunglasses]

You might consider taking a look at the recursion schemes section of my guide here: https://gist.github.com/bitemyapp/8739525

[thewarrior]

Can anyone help me understand how this is different from calculating something iteratively ?

I was reading SICP the other day where they introduced the idea that a process is fundamentally iterative if you just need a few variables to always keep track of the state of the computation.

So tail recursion is iterative and this looks the same. So then why is it called recursion ?

Im a bit confused about this.

[thewarrior]

Edit : Not "few variables" , i meant a fixed single set of variables.

[chriswarbo]

With recursion, we can define something in terms of itself. For example, this is recursive:

    f(n) = f(n - 1) ++ f(n - 1)

Here I'm using "++" to denote list concatenation. Unfortunately this 'diverges', ie. trying to calculate f(x) for any x will keep going forever. There are two ways around this; the first is generally just called "recursion", and it involves fixing a particular "base case", which cuts off the calculation before it becomes infinite, hence causing our function to terminate.

We can do this as follows:

    f(0) = [NULL]

Where "[NULL]" is a list containing NULL. Now we can calculate f(x) for any positive x:

    f(1) = f(0) ++ f(0)
         = [NULL] ++ [NULL]
         = [NULL, NULL]

    f(2) = f(1) ++ f(1)
         = [NULL, NULL] ++ [NULL, NULL]
         = [NULL, NULL, NULL, NULL]

And so on. This kind of code can consume a hell of a lot of resources though, so we may prefer to only write a special kind of recursive function called tail-recursive. Here's a tail-recursive function:

    g(n) = g(n-1)
    g(0) = [0]

This "g" function uses recursion in the same way as "f", but notice that we can switch from calculating g(n) straight to g(n-1), ie. we only transform "n", not g(...). This means we can calculate g in constant space, since we just transform n again and again. Compare this to "f", where we need to calculate f(n-1) separately, then combine the results. Also notice that we don't know anything about the value of "g(x)" until we've finished going down the chain and hit "g(0)".

The other way of preventing divergence is corecursion, which the linked article describes. Here, we must generate a little bit of output before we're allowed to recurse. For example:

    h(n) = cons(n, h(n+1))

This will not terminate, but it will give us some output; specifically:

    h(0) = cons(0, cons(1, cons(2, cons(3, ...))))

We can't "finish" calculating this list, but we don't need to in order to use its elements. We say this function "coterminates", and that it generates "codata".

One interesting fact about co-recursion is that we can turn any diverging function into a coterminating one:

    i(n) = Later(i(n + 1))

This will give an infinite codata structure "Later(Later(Later(Later(...))))". We're effectively breaking down our calculation into steps; after each step, if we're finished we can just give back the result. If we're not finished, we give back a "Later" containing the result of the rest of the calculation.

This forms a really nice structure called the Partial Monad :)

[PurplePanda]

Can anyone say if the difference between recursion and corecursion is the same as the difference between recursive process and iterative process as described in SICP? They seem the same to me. It also seems to be related to the bottom up solving method of dynamic programming.

[midko]

To me, it seems the same as the distinction made in SICP.

As for DP, I think it also comes very close to being the same as the above two. The one difference I can think of is that with DP you often have access to the entire build-up data structure you are creating, rather than only the latest (previous) level you have with an iterative process.

[leephillips]

In Clojure you can generate the Fibonacci sequence with

(def fibs (lazy-cat [0N 1N] (map + fibs (rest fibs))))

which is an example of (memory consuming) corecursion that I managed to sneak into two recent articles:

http://arstechnica.com/science/2014/05/scientific-computings...

and

http://lee-phillips.org/lispmath/

(I did not come up with this.)

[gamegoblin]

Similarly in Haskell:

  fibs = 1:1:zipWith (+) fibs (tail fibs)

[ilozinski]

Corecursive factorial in javascript: https://gist.github.com/i/f75f21f6c56eb55c414c

[hofstee]

Isn't this just bottom up DP?

[highwind]

This is usually how you codify a dynamic programming algorithm. Good to know that there's a name.

[rooted]

Isn't this just the same as Dynamic Programming?

[ggchappell]

> Isn't this just the same as Dynamic Programming?

The two concepts are very related. I would say that corecursion is more low-level and more general. It's also true that DP is not really a computing term. DP is an optimization technique which, when performed using a computer, is often coded using corecursion.

See the comment by chriswarbo[1] for both an excellent explanation and some examples that I don't think we would call DP.

[1] https://news.ycombinator.com/item?id=7721390

[seabee]

This sounds like the algorithmic counterpart to proof by induction.

[chriswarbo]

Actually proof by induction is equivalent to recursion. Corecursion is equivalent to, believe it or not, proof by coinduction ;)

[signa11]

so, generating fractals would be co-recursive then ? :)