  We describe arithmetic computations in terms of operations on some well known
free algebras (S1S, S2S and ordered rooted binary trees) while emphasizing the
common structure present in all them when seen as isomorphic with the set of
natural numbers.
  Constructors and deconstructors seen through an initial algebra semantics are
generalized to recursively defined functions obeying similar laws.
  Implementation using Scala's apply and unapply are discussed together with an
application to a realistic arbitrary size arithmetic package written in Scala,
based on the free algebra of rooted ordered binary trees, which also supports
rational number operations through an extension to signed rationals of the
Calkin-Wilf bijection.

Mathematical Software;Discrete Mathematics;Programming Languages