3 ms·
Some places I find myself using corecursion: Minimax algorithm: https://en.wikipedia.org/wiki/Minimax https://en.wikipedia.org/wiki/Minimax (I actually general
by gamegoblin 12y ago
Some 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 12y 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 12y 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 12y 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 12y agoBasically any unfold is corecursive.