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.
A very nice functional pearl @cite_3 has explored in the past (using Haskell code) algorithms related to the Calkin-Wilf bijection @cite_13 . While using the same underlying mathematics, our Scala-based package works on terms of the AlgT free algebra rather than conventional numbers, and provides a complete package of arbitrary size rational arithmetic operations taking advantage of our generalized constructors.
@cite_13 @cite_3
1982442868 2171866795
2. The function values f(n) actually count something nice. In fact, f(n) is the number of ways of writing the integer n as a sum of powers of 2, each power being used at most twice (i.e., once more than the legal limit for binary expansions). For instance, we can write 5 = 4 + 1 = 2 + 2 + 1, so there are two such ways to write 5, and therefore f(5) = 2. Let’s say that f(n) is the number of hyperbinary representations of the integer n. Every lazy functional programmer knows about the following approach to enumerating the positive rationals: generate a two-dimensional matrix (an infinite list of infinite lists), then traverse its finite diagonals (an infinite list of finite lists).