Histo− and Dynamorphisms Revisited
Dynamic programming algorithms embody a widely used programming technique that optimizes recursively defined equations that have repeating subproblems. The standard solution uses arrays to share common results between successive steps, and while effective, this fails to exploit the structural proper...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Published: |
ACM
2013
|
| _version_ | 1797065125043109888 |
|---|---|
| author | Hinze, R Wu, N |
| author_facet | Hinze, R Wu, N |
| author_sort | Hinze, R |
| collection | OXFORD |
| description | Dynamic programming algorithms embody a widely used programming technique that optimizes recursively defined equations that have repeating subproblems. The standard solution uses arrays to share common results between successive steps, and while effective, this fails to exploit the structural properties present in these problems. Histomorphisms and dynamorphisms have been introduced to expresses such algorithms in terms of structured recursion schemes that leverage this structure. In this paper, we revisit and relate these schemes and show how they can be expressed in terms of recursion schemes from comonads, as well as from recursive coalgebras. Our constructions rely on properties of bialgebras and dicoalgebras, and we are careful to consider optimizations and efficiency concerns. Throughout the paper we illustrate these techniques through several worked-out examples discussed in a tutorial style, and show how a recursive specification can be expressed both as an array-based algorithm as well as one that uses recursion schemes. |
| first_indexed | 2024-03-06T21:24:10Z |
| format | Conference item |
| id | oxford-uuid:42838128-d046-4128-8e84-c3b29a05c0cd |
| institution | University of Oxford |
| last_indexed | 2024-03-06T21:24:10Z |
| publishDate | 2013 |
| publisher | ACM |
| record_format | dspace |
| spelling | oxford-uuid:42838128-d046-4128-8e84-c3b29a05c0cd2022-03-26T14:49:54ZHisto− and Dynamorphisms RevisitedConference itemhttp://purl.org/coar/resource_type/c_5794uuid:42838128-d046-4128-8e84-c3b29a05c0cdDepartment of Computer ScienceACM2013Hinze, RWu, NDynamic programming algorithms embody a widely used programming technique that optimizes recursively defined equations that have repeating subproblems. The standard solution uses arrays to share common results between successive steps, and while effective, this fails to exploit the structural properties present in these problems. Histomorphisms and dynamorphisms have been introduced to expresses such algorithms in terms of structured recursion schemes that leverage this structure. In this paper, we revisit and relate these schemes and show how they can be expressed in terms of recursion schemes from comonads, as well as from recursive coalgebras. Our constructions rely on properties of bialgebras and dicoalgebras, and we are careful to consider optimizations and efficiency concerns. Throughout the paper we illustrate these techniques through several worked-out examples discussed in a tutorial style, and show how a recursive specification can be expressed both as an array-based algorithm as well as one that uses recursion schemes. |
| spellingShingle | Hinze, R Wu, N Histo− and Dynamorphisms Revisited |
| title | Histo− and Dynamorphisms Revisited |
| title_full | Histo− and Dynamorphisms Revisited |
| title_fullStr | Histo− and Dynamorphisms Revisited |
| title_full_unstemmed | Histo− and Dynamorphisms Revisited |
| title_short | Histo− and Dynamorphisms Revisited |
| title_sort | histo and dynamorphisms revisited |
| work_keys_str_mv | AT hinzer histoanddynamorphismsrevisited AT wun histoanddynamorphismsrevisited |