Comparing Use-Cases of Tree-Fold vs Fold-Left, How to Fold and Color a Map

Authors

Jim Newton

Where

Symposium on Implementation and Application of Functional Languages

Place

Copenhagen, Denmark

Type

inproceedings

Projects

AA"AA" 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,
  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. },
  nodoi		= {}
}