Random-Access Lists, from EE to FP
摘要
Numerical representations, which were popularized by Okasaki in his seminal book [1], decouple the design of data-types into, first, a choice of a data-structure encoding a suitable numerical system, followed by decorating this structure with as many pieces of data as specified by the underlying numerical system. This paper ambitions to apply McBride’s theory of ornaments [2] to explore a structural interpretation of numerical representation. In particular, we propose a journey from Electronic Engineering —computing with binary numbers— to Functional Programming —implementing a persistent random-access list datatype.