Breadth-first traversal via staging
An effectful traversal of a data structure iterates over every element, in some predetermined order, collecting computational effects in the process. Depth-first effectful traversal of a tree is straightforward to define compositionally, since it precisely follows the shape of the data. What about b...
| Κύριοι συγγραφείς: | , , , |
|---|---|
| Μορφή: | Conference item |
| Γλώσσα: | English |
| Έκδοση: |
Springer
2022
|
| _version_ | 1826310275826974720 |
|---|---|
| author | Gibbons, J Kidney, DO Schrijvers, T Wu, N |
| author_facet | Gibbons, J Kidney, DO Schrijvers, T Wu, N |
| author_sort | Gibbons, J |
| collection | OXFORD |
| description | An effectful traversal of a data structure iterates over every
element, in some predetermined order, collecting computational effects
in the process. Depth-first effectful traversal of a tree is straightforward
to define compositionally, since it precisely follows the shape of the
data. What about breadth-first effectful traversal? An indirect route is to
factorize the data structure into shape and contents, traverse the contents,
then rebuild the data structure with new contents. We show that this can
instead be done directly using staging, expressed using a construction
related to free applicative functors. The staged traversals lend themselves
well to fusion; we prove a novel fusion rule for effectful traversals, and
use it in another solution to Bird’s ‘repmin’ problem. |
| first_indexed | 2024-03-07T07:49:33Z |
| format | Conference item |
| id | oxford-uuid:229fd94d-6720-41cb-91de-596186ace4cc |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:49:33Z |
| publishDate | 2022 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:229fd94d-6720-41cb-91de-596186ace4cc2023-07-06T15:31:31ZBreadth-first traversal via stagingConference itemhttp://purl.org/coar/resource_type/c_5794uuid:229fd94d-6720-41cb-91de-596186ace4ccEnglishSymplectic ElementsSpringer2022Gibbons, JKidney, DOSchrijvers, TWu, NAn effectful traversal of a data structure iterates over every element, in some predetermined order, collecting computational effects in the process. Depth-first effectful traversal of a tree is straightforward to define compositionally, since it precisely follows the shape of the data. What about breadth-first effectful traversal? An indirect route is to factorize the data structure into shape and contents, traverse the contents, then rebuild the data structure with new contents. We show that this can instead be done directly using staging, expressed using a construction related to free applicative functors. The staged traversals lend themselves well to fusion; we prove a novel fusion rule for effectful traversals, and use it in another solution to Bird’s ‘repmin’ problem. |
| spellingShingle | Gibbons, J Kidney, DO Schrijvers, T Wu, N Breadth-first traversal via staging |
| title | Breadth-first traversal via staging |
| title_full | Breadth-first traversal via staging |
| title_fullStr | Breadth-first traversal via staging |
| title_full_unstemmed | Breadth-first traversal via staging |
| title_short | Breadth-first traversal via staging |
| title_sort | breadth first traversal via staging |
| work_keys_str_mv | AT gibbonsj breadthfirsttraversalviastaging AT kidneydo breadthfirsttraversalviastaging AT schrijverst breadthfirsttraversalviastaging AT wun breadthfirsttraversalviastaging |