[Haskell-beginners] Re: Translating a while

[Heinrich Apfelmus]

Daniel Fischer wrote:
> Am Montag 08 März 2010 14:49:15 schrieb Nicolas Couture-Grenier:
>> I'm learning Haskell and I'm trying to translate a pseudocode algorithm
>> to generate the next permutation from a previous permutation.
> 
> Don't try to translate it directly. In Haskell, generally a different 
> approach than for imperative (pseudo-) code is better.

For instance, like this:

        -- next permutation in lexicographic order
    next :: Ord a => [a] -> Maybe [a]
    next [x]    = Nothing
    next (x:xs) =
        case next xs of
            Nothing -> case span (> x) xs of
                ([],xs) -> Nothing
                (ys,zs) -> Just (last ys : reverse (init ys ++ x : zs))
            Just xs' -> Just (x:xs')

Since there is exactly one permutation that doesn't have a next one, the
result has to be wrapped in a  Maybe  type. Of course, this is very
handy and natural for the recursive formulation of the algorithm anyway.


Since the above definition contains some thought™, here a helper
function to test its correctness:

    permutationsFrom xs = xs : unfoldr (fmap (\x -> (x,x)) . next) xs

    correct n = let perms = permutationsFrom [1..n] in
           length perms == product [1..n]
        &&   sort perms == perms

In other words, repeatedly applying  next  to the trivial permutation
[1..n]  should eventually yield a sorted list of all permutations.

  *Main> correct 8
  True



Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com