# [Haskell-beginners] Re: Translating a while

Heinrich Apfelmus apfelmus at quantentunnel.de
Mon Mar 8 11:07:23 EST 2010

```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

```