Erstellen einer zufälligen Permutation von 1..N mit Data.Vector.Unboxed.Mutable

Question

Ich möchte eine Liste mit einer zufälligen Permutation der Zahlen von 1 bis N erstellen. Wie ich es verstehe, ist es möglich, VUM.swap in der verwenden runST, aber da ich auch Zufallszahlen benötige, dachte ich, ich könnte beides in der IO-Monade machen.

Der folgende Code ergibt:

erwarteten Typ: IO (VU.Vector Int), tatsächliche Typ: IO (VU.Vector (VU.Vector a0))

für die Rücksendeanweisung.

import qualified Data.Vector.Unboxed   as VU 
import qualified Data.Vector.Unboxed.Mutable as VUM 
import   System.Random 

randVector :: Int -> IO (VU.Vector Int) 
randVector n = do 
    vector <- VU.unsafeThaw $ VU.enumFromN 1 n 
    VU.forM_ (VU.fromList [2..VUM.length vector]) $ \i -> do 
    j <- randomRIO(0, i) :: IO Int 
    VUM.swap vector i j 
    return $ VU.unsafeFreeze vector 

Ich bin nicht ganz sicher, warum der Rückkehrvektor verschachtelt ist. Muss ich stattdessen VU.fold1M_ verwenden?

Answer 1

unsafeFreeze vector gibt bereits IO (VU.Vector Int) zurück. Ändern Sie einfach die letzte Zeile in VU.unsafeFreeze vector.

In einem anderen Hinweis sollten Sie bis VUM.length vector - 1 iterieren, da sowohl [x .. y] als auch randomRIO Inclusive-Bereiche verwenden. Sie können auch einfach forM_ hier für Iteration verwenden, da Sie nur für Nebenwirkungen sorgen.

import   Control.Monad 
import qualified Data.Vector.Unboxed   as VU 
import qualified Data.Vector.Unboxed.Mutable as VUM 
import   System.Random 

randVector :: Int -> IO (VU.Vector Int) 
randVector n = do 
    vector <- VU.unsafeThaw $ VU.enumFromN 1 n 
    forM_ [2..VUM.length vector - 1] $ \i -> do 
    j <- randomRIO(0, i) :: IO Int 
    VUM.swap vector i j 
    VU.unsafeFreeze vector 

Ich schaute auf den generierten Code, und es scheint, dass mit GHC 7.10.3 forM_ zu einer effizienten Schleife kompiliert während VU.forM_ die Zwischenliste behält und ist sicherlich deutlich langsamer (das war mein erwartetes Ergebnis für forM_, aber Ich war unsicher über VU.forM_).

Answer 2

Ich würde versuchen, (Anmerkung Update am Ende):

import Control.Monad 

randVector :: Int -> IO (VU.Vector Int) 
randVector n = do 
    vector <- VU.unsafeThaw $ VU.enumFromN 1 n 
    forM_ [2..VUM.length vector] $ \i -> do 
    j <- randomRIO(0, i) :: IO Int 
    VUM.swap vector i j 
    return $ VU.unsafeFreeze vector 

Edit: wie @ András Kovács wies darauf hin, Sie wollen nicht die return am Ende, so dass die letzte Zeile sein sollte:

VU.unsafeFreeze vector