Randomiser une liste dans Haskell

Question

J'essaie, à partir d'une liste, de créer un arrangement aléatoire de ces éléments dans Haskell. J'ai déjà essayé l'algorithme en Javascript et cela a fonctionné. Je suis assez nouveau pour Haskell, donc je ne vois peut-être pas quelque chose. Je suis à peu près sûr que je reçois des éléments simples au lieu de listes avec juste un élément, ce qui fait planter mon programme. J'ai rencontré ce problème dans les exercices précédents mais je ne sais toujours pas comment le résoudre.

L'algorithme divise la liste jusqu'à obtenir un élément. Il y a 50% de chances de fusionner la liste telle qu'elle était et 50% de la fusionner dans l'autre sens.

Voici le code:

-- A randomly chosen, program-scoped constant from the range [1 .. 10] 
randomInt :: Int 
randomInt = unsafePerformIO (getStdRandom (randomR (1, 10))) 

-- Divides the list in half 
divideList :: [a] -> ([a], [a]) 
divideList list = splitAt ((length list) `div` 2) list 

-- Given a list, it creates a new one with the elements of said list 
randomizeList :: Eq a => a -> [a] 
randomizeList list = do 
    let lists = (divideList list) in 
     if (length list) > 1 
     then if (randomInt > 5) 
     then (randomizeList (fst lists) : randomizeList (snd lists)) 
     else (randomizeList (snd lists) : randomizeList (fst lists)) 
     else [list] 

Voici le code Javascript dans le cas où il aide:

function divideList(list){ 
    const length = list.length/2; 
    return {fst: list.splice(0, length), snd: list}; 
} 
function randomizeList(list) { 
    if(list.length == 1) return list; 
    const lists = divideList(list); 
    if(Math.random() > 0.5) return randomizeList(lists.fst).concat(randomizeList(lists.snd)); 
    else return randomizeList(lists.snd).concat(randomizeList(lists.fst)); 
} 

Merci à l'avance

Answer 1

Couple de problèmes avec votre code, des erreurs souvent triviales:

1. signature Wrong, devrait être randomizeList :: Eq a => [a] -> [a] (il est de la liste à la liste, pas de l'élément à la liste)
2. do parasite au début du bloc (supprimez)
3. liste sont concaténés avec ++, pas : (ce dernier ajoute un élément à une liste)
4. dans le dernier else dont vous avez besoin pour revenir list au lieu de [list] (celle-ci est une liste de listes)

Les éléments suivants doivent travailler:

randomizeList :: Eq a => [a] -> [a] 
randomizeList list = 
    let lists = (divideList list) in 
    if (length list) > 1 
    then if (randomInt > 5) 
    then (randomizeList (fst lists) ++ randomizeList (snd lists)) 
    else (randomizeList (snd lists) ++ randomizeList (fst lists)) 
    else list 

Answer 2

Une façon rapide et facile à randomiser une liste serait être:

module Main where                                      

import Control.Monad (replicateM)                        
import Data.Function (on) 
import Data.List  (sortBy) 
import System.Random (randomRIO)                                      

main :: IO() 
main = do                                        
    putStrLn "not randomized"                                    
    let nums = [1..10]                                     
    print nums                                       
    putStrLn "randomized"                                     
    print =<< randomize nums                                    

randomize :: [a] -> IO [a]                                    
randomize xs = do                                      
    ys <- replicateM (length xs) $ randomRIO (1 :: Int, 100000)                           
    pure $ map fst $ sortBy (compare `on` snd) (zip xs ys) 

Ce code génère une liste aléatoire de nombres, les zippe avec la liste d'origine, puis trie ces paires par le nombre aléatoire généré. Nous supprimons ensuite le nombre aléatoire (map fst) et nous nous retrouvons avec la liste d'éléments d'origine, mais aléatoire.

En général, l'utilisation de unsafePerformIO n'est pas recommandée.