Dynamic Programming with Recursion Schemes

Many useful algorithms (shortest path finding, knapsack packing, …) have Dynamic Programming solutions where you break the problem down into subproblems and memoize the solutions. These algorithms usually have nice recursive implementations. And where you have nice recursive solutions (where you typically use recursion directly), you should be able to use a recursion scheme to abstract away that recursion and leave being a more structured declarative program. In this talk, we’ll talk about these recursions schemes: histomorphisms and dynamorphisms, how they are encoded in scala and how you can use them to implement some common dynamic programs.

Session length

40 minutes

Language of the presentation

English

Target audience

Advanced: For those who are experts in the field

Who is your session intended to

People who have some idea about recursion schemes are would like to dig deeper.

Speaker

Ratan Sebastian (commercetools)