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

From LRDE

Revision as of 11:22, 3 December 2022 by Bot (talk | contribs)

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