Numerals in Positional Notation   [11]

A concrete algorithm (reversed results)

We can take divMod to be the basic step in a recursive algorithm which extracts the digits of a number in base b step by step (here we will concentrate on producing a list of Ints: conversion to actual digit symbols is merely a map away). In the recursive case, we take a number n and extract two numbers from it using divMod, namely the remainder after division by b (call this r) and a new number m which is the basis for the next step in the process. We call this function str to remind us that it converts a number to a String (once we convert to digits). When we reach 0 there is nothing left to process, so we will return an empty list.

Unfortunately, the natural recursive algorithm returns the digits in the reverse of the order we really want: this is the same problem we encountered when converting numerals to numbers, now hitting us on the ass as we go back out the door.

str b 0 = []
str b n = r : str b m
          where (m,r) = n `divMod` b

> str 10 1234
[4,3,2,1]
> str 2 13
[1,0,1,1]

Notes

• recall that enclosing an alphabetic identifier like divMod in back-quotes converts it (syntactically) into an infix operator:

  n `divMod` b == divMod n b

• for 13, the answer in binary should be "1101" or [1,1,0,1]