HW8 - Nonstandard Integers in Haskell

This assignment has two parts. The first is a fun warm-up exercise, the second an even more fun stripped down combination of extended precision integers and manipulation of power series.

Warm-up exercise

Please recall the trick for putting the positive rational numbers in one-to-one correspondence with the natural numbers. I think it is covered in CS 201, but I'll review it here. Given an infinite 2D table of fractions

1/1 2/1 3/1 4/1 5/1 ...
1/2 2/2 3/2 4/2 5/2 ...
1/3 2/3 3/3 4/3 5/3 ...
1/4 2/4 3/4 4/4 5/4 ...
1/5 2/5 3/5 4/5 5/5 ...
.         .    .    .
.         .     .     .
.         .      .      .

you run through it in diagonal slices to create a 1D sequence that eventually gets to every entry in the 2D table, as follows

1/1   2/1 1/2   3/1 2/2 1/3   4/1 3/2 2/3 1/4   5/1 4/2 3/3 2/4 1/5   ...

Your task is to write a function diag

$ hugs
Main> :load diag.hs
Main> :t diag
diag :: [[a]] -> [a]

which embodies this transformation. You pass diag an infinite list of infinite lists, and it returns an infinite list, formed in the fashion above, of all the elements in the structure it was passed.

For example, with the definitions in this file

-- Take a list of lists, all potentially infinite.  Return a single
-- list which hits each element after some time.

{- -- commented out, sorry!
diag :: [[a]] -> [a]
diag x = ... skipping a few lines ...
-}

-- The standard table of all positive rationals, in three forms:
-- (1) as floats
rlist = [ [i/j | i<-[1..]]  |  j <- [1..] ]
-- (2) as strings, not reducd
qlist1 = [ [show i ++ "/" ++ show j | i<-[1..]]  |  j <- [1..] ]
-- (3) as strings, in reduced form
qlist2 = [ [fracString i j | i <- [1..]]  |  j <- [1..] ]

-- take a numerator and denominator, reduce, and return as string
fracString num den = if denominator == 1
                 then show numerator
                 else show numerator ++ "/" ++ show denominator
    where c = gcd num den
          numerator = num `div` c
          denominator = den `div` c

-- Take an n-by-n block from the top of a big list of lists
block n x = map (take n) (take n x)

you should be able to do this (whitespace changed for readability):

$ hugs

Main> :load diag.hs
Reading file "diag.hs":
Hugs session for:
/usr/share/hugs98/lib/Prelude.hs
diag.hs

Main> block 5 qlist2
 [["1",   "2",   "3",   "4",   "5"],
  ["1/2", "1",   "3/2", "2",   "5/2"],
  ["1/3", "2/3", "1",   "4/3", "5/3"],
  ["1/4", "1/2", "3/4", "1",   "5/4"],
  ["1/5", "2/5", "3/5", "4/5", "1"]]

Main> take 20 (diag qlist2)
 ["1",
  "2", "1/2",
  "3", "1", "1/3",
  "4", "3/2", "2/3", "1/4",
  "5", "2", "1", "1/2", "1/5",
  "6", "5/2", "4/3", "3/4", "2/5"]

Extended extended precision integers

You will implement a datatype of infinite precision non-negative integers, represented as a list of digits in base ten starting at the least significant digit and going up. (Your code should actually be modular so you could change the base by changing only one definition of a constant.) You should define a datatype LongNat, and functions as follows:

toLongNat takes a (possibly infinite) list of digits and returns a LongNat.
intLongNat takes a regular (nonnegative) Haskell integer and returns a LongNat.
takeLongNat takes a number n and a LongNat x, returns a list of the first n digits of x, least significant first. The list may terminate early if you run out of digits, just like regular take as in take 20 [1,2,3].
addLongNat takes two LongNats and returns their sum, as a LongNat.
mulLongNat takes two LongNats and returns their product, as a LongNat.
subLongNat takes two LongNats and returns the first minus the second, as a LongNat. We will not check for correctness in the case where the result would be negative. (However, you will get style points for handling ``negatives'' in fashion hinted at in the examples below.)
fromLongNat takes a LongNat and converts it to a regular Haskell integer. Returns bottom (ie never returns) when given a nonstandard integer (ie a LongNat whose list of digits never terminates.)
zeroLongNat takes a LongNat x and returns true iff x is zero. Returns bottom when given a nonstandard integer.
geqLongNat takes two LongNats x and y, and returns true iff x is greater than or equal to y. Given two nonstandard integers, this will return bottom.

The big twist in this is that LongNat must handle not only conventional natural numbers, but also a certain kind of so-called non-standard integers, namely numbers with an infinite number of digits. Writing the least significant digit first, consider the number

1 2 1 2 1 2 ...

or in more conventional notation the infinite number ...2121212121212121. Loosely speaking, this corresponds to the divergent sum

1 + 2*10 + 1*100 + 2*1000 + 1*10000 + 2*100000 + ...

sum_{i=0..infinity} s_i 10ⁱ
where s₀ = 1, s₁ = 2, s₂ = 1, s₃ = 2, s₄ = 1, s₅ = 2, etc.

We can create a LongNat with this value by first making an infinite list of digits and then calling toLongNat on it, as in

 list12 = 1 : 2 : list12
 x = toLongNat list12

Now the interesting thing to note is that it is possible to do arithmetic on these nonstandard integers. We just treat them like regular numbers and do arithmetic, lining up the digits, adding, and (most important) carrying as usual. Let's build and play with some. We :load a file with the definition

circularize x = y where y = x ++ y

and now

Main> take 20 (circularize [1])
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

Main> take 20 (circularize [1,1,2])
[1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1]

Main> takeLongNat 10 (intLongNat 613)
[3,1,6]

Main> takeLongNat 13 (intLongNat 37125436219876543210)
[0,1,2,3,4,5,6,7,8,9,1,2,6]

Main> takeLongNat 20 (addLongNat (toLongNat (circularize [1]))
                                 (toLongNat (circularize [1,1,2])))
[2,2,3,2,2,3,2,2,3,2,2,3,2,2,3,2,2,3,2,2]

Main> takeLongNat 20 (mulLongNat (toLongNat [1,5])
                                 (toLongNat (circularize [1])))
[1,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6]

Main> takeLongNat 30 (mulLongNat (toLongNat (circularize [1]))
                                 (toLongNat (circularize [1])))
[1,2,3,4,5,6,7,8,9,0,2,3,4,5,6,7,8,9,0,2,3,4,5,6,7,8,9,0,2,3]

Main> takeLongNat 20 (addLongNat (toLongNat (circularize [9]))
                                 (toLongNat [1]))
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Main> takeLongNat 20 (addLongNat (toLongNat [8]++(circularize [9]))
                                 (intLongNat 2))
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Important: when the list of digits terminates, you have a standard integer. When it doesn't terminate, you have a nonstandard one. Since you cannot tell which is which in finite time, your code must handle both uniformly. So, to make standard numbers work your code has to handle things correctly when the list of digits terminates. And to make it handle nonstandard ones correctly, it has to handle things correctly when they don't. And this has to be the case even though you don't know which you happen to be dealing with.

Hint: one way to handle the arithmetic is in two phases, first you add or multiply or subtract as if there were no carrying, so single "digits" can go above or below the base. Then you have a function called something like rippleCarry, which takes the list of possibly-overflown digits and carrys up. So eg rippleCarry [0,17,1,8,12,9] would return [0,7,2,8,2,0,1].

Hint: Haskell numbers can be tricky. Avoid getting to floats by staying with integers. In particular

Prelude> :t (/)
(/) :: Fractional a => a -> a -> a

Prelude> :t div
div :: Integral a => a -> a -> a

which means you're better off using div for division, because if you use / you'll get a float which you will probably find annoying. The mod function is also useful.

Extra Credit

For extra credit, figure out enough about the Haskell class system to plug into it, so that your LongNat type can be used with the usual numeric class hierarchy, is an ordinal class, etc. When you do this you don't have to implement all kinds of new processing, you can just return bottom for all the necessary function stubs that correspond to functionality not required above.

Handing in your solution

Your files should contain everything necessary for the assignment. Do not run the script several times to hand in different portions of the assignment, turn in all files at once, each time.

Please be sure your file loads and runs properly on hugs as installed on the CS machines. Turn it in by running eg

~bap/bin/handin buzzlightyear.hs

on a regular UNM CS machine. (Though the above has just one file, you can include more than one if appropriate.)

Due: 3:30pm, Dec 10. If you want an extension, you can have an automatic one until 9am Fri Dec 14. But you're better off finishing this before the final exam, so you'll know Haskell when you take the exam!

Barak Pearlmutter <bap@cs.unm.edu>