[Haskell-beginners] Translating a while

[Daniel Fischer]

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.

>
> A permutation is a list of n numbers (let's call it a) in {1 .. n}
> appearing once in arbitrary order.
>
> The first step is to find the largest index j in the list for which a[j]
> < a[j+1].
>
> The pseudocode is simple:
>
> j:= n-1
>
> while a[j] > a[j+1]
>     j:=j-1
>
>
> I've coded a haskell function to do this, but it is much uglier than the
> pseudocode :

It's not appropriate for lists, therefore, it's ugly. You can work with 
arrays and have a fairly direct correspondence:

import Data.Array

fun :: Array Int Int -> Int
fun a = go (hi-1)
   where
      (lo,hi) = bounds a
      go i
        | i < lo        = i
        | a!i > a!(i+1) = go (i-1)
        | otherwise     = i

The local "go" is our while-loop, additionally, it checks that we don't 
fall off the front of the array.

When working with lists, one would typically not produce the next 
permutation from the previous, but generate the list of all permutations 
(take a look at the code of "permutations" in Data.List).

>
> j :: Integral a => [a] -> Int
> j [] = 0
> j xs = if (head (tail (reverse xs)) < last xs)
>           then (length xs)-2
>           else j (take (length xs - 1) xs)
>
>
> Does anyone has a more elegant solution for this first step?