<br><div class="gmail_quote">On Nov 14, 2007 12:32 PM, Kurt Hutchinson &lt;<a href="mailto:kelanslists@gmail.com">kelanslists@gmail.com</a>&gt; 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&#39;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 -&gt; map (\ p -&gt; n ^ p ) [ 2 .. ] ) [ 2 .. ]<br><br>next ( _, ( lim, ps ) ) =<br> &nbsp; &nbsp;( p, ( lim&#39;, ps&#39; ) )<br> &nbsp; &nbsp;where<br> &nbsp; &nbsp;( c, p ) = minimumBy ( compare `on` snd ) . zip [ 0 .. lim ] .
<br>head . transpose $ ps<br> &nbsp; &nbsp;lim&#39; = lim + ( if c == lim then 1 else 0 )<br> &nbsp; &nbsp;( front, b : back ) = splitAt c ps<br> &nbsp; &nbsp;ps&#39; = front ++ ( tail b : back )<br><br>-- like the unix utility<br>uniq [] = []<br>uniq [x] = [x]
<br>uniq (x:y:ys)<br> &nbsp; &nbsp;| x == y &nbsp; &nbsp;= &nbsp; &nbsp; uniq (y:ys)<br> &nbsp; &nbsp;| 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&#39;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&#39;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) =&gt; [a] -&gt; [a] -&gt; [a]<br>[] # ys = ys
<br>xs # [] = xs<br>xs@(x:xt) # ys@(y:yt) | x &lt; y = x : (xt # ys)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | x &gt; y = y : (xs # yt)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | 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) =&gt; [[a]] -&gt; [a]<br>mergeAll ([] : zs) = mergeAll zs<br>mergeAll (xxs@(x:xs) : yys@(y:ys) : zs)<br>&nbsp;&nbsp;&nbsp; | x &lt; y = x : mergeAll (xs : yys : zs)
<br>&nbsp;&nbsp;&nbsp; | 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.&nbsp; Summing the first 7000 powers took ~8s and ~0.1s respectively, so that&#39;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&#39;m not exactly sure why that would be the case.
<br><br>-Brent<br></div>