Numerals in Positional Notation   [13]

Abstracting the recursive structure

As we did with the foldr and foldl functions previously, we can try to abstract out the recursive structure of the algorithm so that we can re-use it in other situations. A first attempt, shown below, gives us an algorithm which we will call unfoldl, since it "unfolds" a number from the left into a list. (There is a traditional notion of unfolding in the Haskell List library which is similar to an abstracted version of our original reversed definition: it is called unfoldr, but its type and definition are complicated by other considerations.)

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

str b = unfoldl (`divMod` b) []

unfoldl f a 0 = a
unfoldl f a n = unfoldl f (r:a) m
                where (m,r) = f n

Notes

• the type of our unfoldl function is as follows:

  unfoldl :: (Int -> (Int,b)) -> [b] -> Int -> [b]