Premium
Easily solving dynamic programming problems in Haskell by memoization of hylomorphisms
Author(s) -
Llorens David,
Vilar Juan Miguel
Publication year - 2020
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.2887
Subject(s) - memoization , haskell , computer science , dynamic programming , exponential function , mathematical optimization , programming language , algorithm , functional programming , mathematics , mathematical analysis , parsing , top down parsing
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.