[Haskell-cafe] List of all powers

[Kurt Hutchinson]

As part of a solution I'm working on for Project Euler problem 119, I
wanted to create an ordered list of all powers of all positive
integers (starting with squares). This is what I came up with:

powers = ( uniq . map fst . iterate next ) ( 1, ( 0, powertable ) )

powertable = map (\ n -> map (\ p -> n ^ p ) [ 2 .. ] ) [ 2 .. ]

next ( _, ( lim, ps ) ) =
    ( p, ( lim', ps' ) )
    where
    ( c, p ) = minimumBy ( compare `on` snd ) . zip [ 0 .. lim ] .
head . transpose $ ps
    lim' = lim + ( if c == lim then 1 else 0 )
    ( front, b : back ) = splitAt c ps
    ps' = front ++ ( tail b : back )

-- like the unix utility
uniq [] = []
uniq [x] = [x]
uniq (x:y:ys)
    | x == y    =     uniq (y:ys)
    | otherwise = x : uniq (y:ys)

Basically, think of a grid of numbers, each row is the list of powers
for one integer. To find the next power in the sequence, look at the
the first number in each row (since that will be the smallest number
in the row), up to limit number of rows. The limit is calculated as
the number of rows that we've already taken one number from, plus one.
This exploits the fact that the row heads are initially ordered. If we
use a number from a row, shift that row down to remove the number
used.

It does pretty well, but I'd welcome any comments, or even suggestions
of a completely different algorithm (for this little exercise, or
problem 119). Thanks.

Kurt Hutchinson