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 function diag1/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 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.$ 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"]
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
sumi=0..infinity si 10iWe can create a LongNat with this value by first making an infinite list of digits and then calling toLongNat on it, as in
where s0 = 1, s1 = 2, s2 = 1, s3 = 2, s4 = 1, s5 = 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. We :load a file with the definitionlist12 = 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 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.Prelude> :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!