8 ms·
Corecursion
- gamegoblin 13y agoSome places I find myself using corecursion: Minimax algorithm: https://en.wikipedia.org/wiki/Minimax 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.
- XaspR8d 13y agoDang it. Every time I see something like this, I really get excited for this summer when I have time blocked off for learning Haskell.
- zwegner 13y ago> Minimax algorithm: https://en.wikipedia.org/wiki/Minimax 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.
- gamegoblin 13y agoYou're correct about the minimax. The second example is corecursion, I believe. The article specifically mentions > Corecursion can produce both finite and infinite data structures as result, and may employ self-referential data structures. Corecursion is often used in conjunction with lazy evaluation
- tel 13y agoBasically any unfold is corecursive.
- deleted 13y ago[deleted]
- adamnemecek 13y agoI posted this since I didn't know it had a name.
- coolsunglasses 13y agoYou might consider taking a look at the recursion schemes section of my guide here: https://gist.github.com/bitemyapp/8739525 https://gist.github.com/bitemyapp/8739525
- crashandburn4 13y agoAm 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?
- Sharlin 13y agoI 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.
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- tel 13y agoThose 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)
- hofstee 13y agoIsn't this just bottom up DP?
- Pitarou 13y agoThis 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. :-)
- gamegoblin 13y agoAlternatively, making use of laziness and recursive definitions: fibonacci n = fibs !! n fibs = 1:1:zipWith (+) fibs (tail fibs)
- Pitarou 13y agoYour version is certainly pretty, and it's based on an insight into the nature of the fibonacci series But the value of co-recursion is that you don't need that insight. When you expand out the definitions of `tail`, `!!` and `zipWith`, your code turns out to be the same as mine[1], so I consider that a big win for co-recursion. [1]: At least I think it does.
- Osmium 13y ago> But this is ridiculously inefficient. I'm sorry, but I don't understand this. How is that inefficient?
- Aqwis 13y agoIt makes two recursive calls at each step.
- highwind 13y agoThis is usually how you codify a dynamic programming algorithm. Good to know that there's a name.
- leephillips 13y agoIn 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-future-can-any-coding-language-top-a-1950s-behemoth/ http://arstechnica.com/science/2014/05/scientific-computings... and http://lee-phillips.org/lispmath/ http://lee-phillips.org/lispmath/ (I did not come up with this.)
- gamegoblin 13y agoSimilarly in Haskell: fibs = 1:1:zipWith (+) fibs (tail fibs)
- rooted 13y agoIsn't this just the same as Dynamic Programming?
- ggchappell 13y ago> 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 https://news.ycombinator.com/item?id=7721390
- Dn_Ab 13y agoAnalogies 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 13y agoWhat 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.
- tel 13y agolength . repeat won't type either. Briefly, recursion and corecursion have the following types cata : (f a -> a) -> mu f -> a ana : (a -> f a) -> a -> nu f where `mu` is the "least fixed point" of a base functor f and `nu` the "greatest fixed point". In non-terminal, non-strict languages `mu f == nu f`, but in total languages they don't. We call types of the form `mu f` data and types of the form `nu f` codata. Data is guaranteed to be finite while codata is not.
- oggy 13y agoThanks. Is there a way to type something like take 5 . repeat? Or more generally, how do you make use of codata in these languages?
- tel 13y agoYou think of it like a generator. Before I wrote something like ana : Step f seed -> seed -> Nu f but we might define `Nu f` using an existential to just be data Nu f = forall seed . (Step f seed, seed) and then you can write an eliminator for this type which just handles each step. So, `repeat` might look like data ListF a x = Nil | Cons a x repeat :: a -> Nu (ListF a) repeat a = Nu (\x -> Cons x x, a) and then `take` will be a parametric catamorphism on Nat which just repeatedly creates new layers and consumes them. Together these form a thing called a hylomorphism.
- ilozinski 13y agoCorecursive factorial in javascript: https://gist.github.com/i/f75f21f6c56eb55c414c https://gist.github.com/i/f75f21f6c56eb55c414c
- PurplePanda 13y agoCan 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 13y agoTo 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.
- signa11 13y agoso, generating fractals would be co-recursive then ? :)
- seabee 13y agoThis sounds like the algorithmic counterpart to proof by induction.
- chriswarbo 13y agoActually proof by induction is equivalent to recursion. Corecursion is equivalent to, believe it or not, proof by coinduction ;)
- thewarrior 13y agoCan 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 13y agoEdit : Not "few variables" , i meant a fixed single set of variables.
- chriswarbo 13y agoWith 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 :)