[Haskell-beginners] permuting a list

[Brent Yorgey]

On Thu, Feb 12, 2009 at 10:20:32AM +0100, Jan Snajder wrote:
> 
> this is what I get:
> 
> <interactive>:1:0:
>     No instance for (MArray a1 t IO)
>       arising from a use of `permute' at <interactive>:1:0-14
>     Possible fix: add an instance declaration for (MArray a1 t IO)
>     In the expression: permute [1, 2, 3]
>     In the definition of `it': it = permute [1, 2, 3]
> 
> How can I fix this?
> 

<rant>
It seems everyone has just been reading the first few words of Jan's
email and not the actual content.  Jan is clearly trying to write a
*random list shuffling* function, not a function to generate
permutations.  Let's try to be helpful, people...
</rant>

Jan, this is tricky.  The type of permute is indeed (MArray a1 a IO)
=> [a] -> IO [a], but this is fine, it just means that there has to be
some sort of mutable array which can store the things you are trying
to shuffle.  This is not the problem.  The problem seems to be that
Haskell has no way to know what sort of array you want to use.  I was
able to get the code to work, but it's sort of sneaky:

> {-# LANGUAGE FlexibleContexts, ScopedTypeVariables #-}

> import Data.Array.MArray
> import Data.Array.IO
> import Control.Monad
> import System.Random

> permute :: forall a. (MArray IOArray a IO) => [a] -> IO [a]
> permute xs = do
>   let n = length xs - 1
>   arr0 <- (newListArray (0, n) xs :: IO (IOArray Int a))
>   arr <- foldM swap arr0 [n..1]
>   getElems arr
>   where swap arr n = do
>           x <- readArray arr n
>           r <- randomRIO (0, n)
>           y <- readArray arr r
>           writeArray arr n y
>           writeArray arr r x
>           return arr

We have to give an explicit type annotation on the newListArray, to
tell Haskell what kind of array we want to use. But then we also need
to use the ScopedTypeVariables extension, so that the 'a' in the type
signature for permute scopes over the definition, so that Haskell
knows we want the 'a' in the IOArray Int a to be the same type as the
'a' in the type signature.  Otherwise it doesn't know they are the
same and complains.

Also, when I try running permute, it seems to be the identity
function, but I guess that's a separate issue!

-Brent