you run through it in diagonal slices to create a 1D sequence that eventually gets to every entry in the 2D table, as follows1/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 ... . . . . . . . . . . . .

Your task is to write a function1/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 ...

which embodies this transformation. You pass$ hugs Main> :load diag.hs Main> :t diag diag :: [[a]] -> [a]

For example, with the definitions in this file

you should be able to do this (whitespace changed for readability):-- 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)

$ 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"]

`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.

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 + ...or

sumWe can create a LongNat with this value by first making an infinite list of digits and then calling_{i=0..infinity}s_{i}10^{i}

where s_{0}= 1, s_{1}= 2, s_{2}= 1, s_{3}= 2, s_{4}= 1, s_{5}= 2, etc.

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. Welist12 = 1 : 2 : list12 x = toLongNat list12

and nowcircularize x = y where y = x ++ y

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

which means you're better off usingPrelude> :t (/) (/) :: Fractional a => a -> a -> a Prelude> :t div div :: Integral a => a -> a -> a

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

on a regular UNM CS machine. (Though the above has just one file, you can include more than one if appropriate.)~bap/bin/handin buzzlightyear.hs

*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>