# Comparing Use-Cases of Tree-Fold vs Fold-Left, How to fold and color a map

### From LRDE

- 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. } }