<br><div class="gmail_quote">On Nov 14, 2007 12:32 PM, Kurt Hutchinson <<a href="mailto:firstname.lastname@example.org">email@example.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
As part of a solution I'm working on for Project Euler problem 119, I<br>wanted to create an ordered list of all powers of all positive<br>integers (starting with squares). This is what I came up with:<br><br>powers = ( uniq . map fst . iterate next ) ( 1, ( 0, powertable ) )
<br><br>powertable = map (\ n -> map (\ p -> n ^ p ) [ 2 .. ] ) [ 2 .. ]<br><br>next ( _, ( lim, ps ) ) =<br> ( p, ( lim', ps' ) )<br> where<br> ( c, p ) = minimumBy ( compare `on` snd ) . zip [ 0 .. lim ] .
<br>head . transpose $ ps<br> lim' = lim + ( if c == lim then 1 else 0 )<br> ( front, b : back ) = splitAt c ps<br> ps' = front ++ ( tail b : back )<br><br>-- like the unix utility<br>uniq  = <br>uniq [x] = [x]
<br>uniq (x:y:ys)<br> | x == y = uniq (y:ys)<br> | otherwise = x : uniq (y:ys)<br><br>Basically, think of a grid of numbers, each row is the list of powers<br>for one integer. To find the next power in the sequence, look at the
<br>the first number in each row (since that will be the smallest number<br>in the row), up to limit number of rows. The limit is calculated as<br>the number of rows that we've already taken one number from, plus one.
<br>This exploits the fact that the row heads are initially ordered. If we<br>use a number from a row, shift that row down to remove the number<br>used.<br><br>It does pretty well, but I'd welcome any comments, or even suggestions
<br>of a completely different algorithm (for this little exercise, or<br>problem 119). Thanks.<br><font color="#888888"></font></blockquote><br>The merging can be done much more simply and efficiently (this is code I wrote when computing squarefree numbers in
<a href="http://byorgey.wordpress.com/2007/09/01/squarefree-numbers-in-haskell/">a blog post</a> a few months ago):<br><br>-- merge two nondecreasing lists.<br>( # ) :: (Ord a) => [a] -> [a] -> [a]<br> # ys = ys
<br>xs #  = xs<br>xs@(x:xt) # ys@(y:yt) | x < y = x : (xt # ys)<br> | x > y = y : (xs # yt)<br> | otherwise = x : (xt # yt)<br><br>-- merge an infinite list of lists, assuming that each list
<br>-- is nondecreasing and the lists occur in order of their first<br>-- element.<br>mergeAll :: (Ord a) => [[a]] -> [a]<br>mergeAll ( : zs) = mergeAll zs<br>mergeAll (xxs@(x:xs) : yys@(y:ys) : zs)<br> | x < y = x : mergeAll (xs : yys : zs)
<br> | otherwise = mergeAll ((xxs # yys) : zs)<br><br><br>Then you can simply define<br><br>powers = 1 : mergeAll powertable<br><br>I wrote some code to sum the first n powers and print the result, and compiled (using -O2) first with your method, then with mergeAll. Summing the first 7000 powers took ~8s and ~0.1s respectively, so that's a pretty big speedup. Based on seeing how the times scale, I suspect that your code is O(n^2) or something of that sort, whereas mergeAll is essentially linear, although without scrutinizing your code more closely I'm not exactly sure why that would be the case.