Numerals in Positional Notation

This lecture develops a couple of approaches to the problem of expressing and processing numbers via their representations as numerals in fixed-radix positional notation. We will use lists of digits in Haskell, although the issue of what should constitute a digit will be one of the first issues we explore. For simplicity, we will assume that the target meanings (semantics) will be in terms of meta-language integers (i.e., Haskell Ints or Integers). Another natural choice (sorry!) would be to use the Peano-style representations developed in the earlier lecture, which have the advantage that they more accurately represent the domain intended here (i.e., we won't be concerned with negative numbers).

Note: this lecture is currently just a skeleton! But see this code file

Contents

•   Where does positional notation come from?
•   Representation of digits
•   Programming with powers
•   Consolidation of powers code
•   Breaking positional notation down recursively
•   Folding from the right and left
•   Using foldr on reversed digits
•   Origins of foldl: accumulation and reverse
•   Horner's technique: folding from the left
•   Reversing the process: showing numbers
•   A concrete algorithm (reversed results)
•   Using an accumulating parameter
•   Abstracting the recursive structure
•   Abstracting from the numeric structure
•   Final code consolidation