Easily solving dynamic programming problems in Haskell by memoization of hylomorphisms. (17th September 2020)

• Record Type: Journal Article
• Authors: Llorens, David; Vilar, Juan Miguel
• Is Part Of: Software, practice & experience. Volume 50:Number 12(2020)
• Page Start: 2193
• Page End: 2211
• Publication Date: 2020-09-17
• Subjects: dynamic programming -- Haskell -- memoization -- recursion schemes; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2887
• Languages: English
• ISSNs: 0038-0644

Abstract

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.