Easily solving dynamic programming problems in Haskell by memoization of hylomorphisms. (17th September 2020) - Llorens, David; Vilar, Juan Miguel
Summary: Dynamic programming is a well‐known algorithmic technique that solves problems by a combination of dividing a problem into subproblems and using memoization to avoid an exponential growth of the costs. We show how to implement dynamic programming in Haskell using a variation of hylomorphisms that includes memoization. Our implementation uses polymorphism so the same function can return the best score or the solution to the problem based on the type of the returned value.