Difference between revisions of "Publications/newton.22.ifl"
From LRDE
(Created page with "{{Publication | published = true | date = 2022-08-31 | authors = Jim Newton | title = Comparing Use-Cases of Tree-Fold vs Fold-Left, How to fold and color a map | booktitle =...") |
|||
Line 10: | Line 10: | ||
| lrdeprojects = Automata |
| lrdeprojects = Automata |
||
| address = Copenhagen, Denmark |
| address = Copenhagen, Denmark |
||
− | | abstract = In this article we examine some consequences of computation order of two different conceptual implementations of the fold function. |
+ | | abstract = In this article we examine some consequences of computation order of two different conceptual implementations of the fold function. We explore a set of performance- and accuracy-based experiments on two implementations of this function. In particular, we contrast the traditional fold-left implementation with another approach we refer to as tree-fold. It is often implicitly supposed that the binary operation in question has constant complexity. We explore several application areas which diverge from that assumption: rational arithmetic, floating-point arithmetic, and Binary Decisions Diagram construction. These are binary operations which degrade in performance as the fold iteration progresses. We show that these types of binary operations are good candidates for tree-fold. |
| type = inproceedings |
| type = inproceedings |
||
| id = newton.22.ifl |
| id = newton.22.ifl |
Revision as of 15:20, 6 September 2022
- Authors
- Jim Newton
- Where
- Symposium on Implementation and Application of Functional Languages
- Place
- Copenhagen, Denmark
- Type
- inproceedings
- Projects
- Automata"Automata" is not in the list (Vaucanson, Spot, URBI, Olena, APMC, Tiger, Climb, Speaker ID, Transformers, Bison, ...) of allowed values for the "Related project" property.
- Keywords
- fold, scala, BDD, associativity, binary decision diagram, lisp, rational numbers
- Date
- 2022-08-31
Abstract
In this article we examine some consequences of computation order of two different conceptual implementations of the fold function. We explore a set of performance- and accuracy-based experiments on two implementations of this function. In particular, we contrast the traditional fold-left implementation with another approach we refer to as tree-fold. It is often implicitly supposed that the binary operation in question has constant complexity. We explore several application areas which diverge from that assumption: rational arithmetic, floating-point arithmetic, and Binary Decisions Diagram construction. These are binary operations which degrade in performance as the fold iteration progresses. We show that these types of binary operations are good candidates for tree-fold.
Bibtex (lrde.bib)
@InProceedings{ newton.22.ifl, author = {Jim Newton}, title = {Comparing Use-Cases of Tree-Fold vs Fold-Left, How to fold and color a map}, booktitle = {Symposium on Implementation and Application of Functional Languages}, year = 2022, lrdestatus = {accepted}, address = {Copenhagen, Denmark}, month = aug, abstract = {In this article we examine some consequences of computation order of two different conceptual implementations of the fold function. We explore a set of performance- and accuracy-based experiments on two implementations of this function. In particular, we contrast the traditional fold-left implementation with another approach we refer to as tree-fold. It is often implicitly supposed that the binary operation in question has constant complexity. We explore several application areas which diverge from that assumption: rational arithmetic, floating-point arithmetic, and Binary Decisions Diagram construction. These are binary operations which degrade in performance as the fold iteration progresses. We show that these types of binary operations are good candidates for tree-fold. } }