Как случайным образом перемешать список - PullRequest
Новая
       28

Как случайным образом перемешать список

0 голосов
/ 26 февраля 2020

У меня есть генератор случайных чисел 

rand :: Int -> Int -> IO Int
rand low high = getStdRandom (randomR (low,high))

и вспомогательная функция для удаления элемента из списка 

removeItem _ []                 = []
removeItem x (y:ys) | x == y    = removeItem x ys
                    | otherwise = y : removeItem x ys

Я хочу перетасовать данный список путем случайного выбора элемента из список, удалив его и добавив его в начало списка. Я пытался 

shuffleList :: [a] -> IO [a]
shuffleList [] = []
shuffleList l = do 
                     y <- rand 0 (length l)
                     return( y:(shuffleList (removeItem  y l) ) )

Но не могу заставить его работать. Я получаю 

hw05.hs:25:33: error:
    * Couldn't match expected type `[Int]' with actual type `IO [Int]'
    * In the second argument of `(:)', namely
     ....

Есть идеи?

Спасибо!

Ответы [ 2 ]

2 голосов
/ 26 февраля 2020

Так как shuffleList :: [a] -> IO [a], у нас есть shuffleList (xs :: [a]) :: IO [a].

Очевидно, что мы не можем (:) :: a -> [a] -> [a] * a элемент * преобразовать в IO [a] значение, но вместо этого мы хотим использовать его в список [a], вычисление которого описывает это значение IO [a]: 

   do
         y <- rand 0 (length l)
         -- return ( y : (shuffleList (removeItem  y l) ) )
         shuffled  <-     shuffleList (removeItem  y l)
         return      y : shuffled

В обозначениях do значения справа от <- имеют типы M a, M b, et c., для некоторой монады M (здесь IO), а значения слева от <- имеют соответствующие типы a, b, et c ..

x :: a в x <- mx привязывается к чистому значению типа a, полученному / вычисленному с помощью вычисления M -типа, значение которого mx :: M a обозначает , когда это вычисление фактически выполняется как часть комбинированного вычисления, представленного целым блоком do, когда это комбинированное вычисление выполняется как единое целое.

И если, например, следующая строка в этом do блок равен y <- foo x, это означает, что к x применяется чистая функция foo :: a -> M b, и вычисляется результат, который является значением t ype M b, обозначающий вычисление M -типа, которое затем выполняется и производит / вычисляет чистое значение типа b, к которому затем привязывается имя y.

Суть Monad заключается в том, что таким образом, это разделение чистых внутри / между (потенциально) нечистыми , именно эти две временные шкалы происходят из чистых вычислений и потенциально нечистых вычисления , с чистым миром, надежно отделенным и изолированным от примесей реального мира. Или, с другой стороны, чистый код, выполняемый реальным нечистым кодом, взаимодействующим с реальным миром (в случае M равен IO). Вот что компьютерные программы должны делать, в конце концов.

Ваш removeItem неверен. Вы должны выбирать и удалять элементы позиционно, то есть по индексу, а не по значению; и ни в коем случае не удаляйте более одного элемента после выбора одного элемента из списка.

y в y <- rand 0 (length l) действительно является индексом. Относитесь к этому как таковой. Переименуйте его в i тоже как простой мнемон c.

0 голосов
/ 26 февраля 2020

Как правило, с Haskell лучше работает, чтобы максимизировать количество функционального кода за счет нефункционального (IO или случайного) кода.

В вашей ситуации ваш «максимальный» функциональный компонент - это не removeItem, а скорее версия shuffleList, которая принимает входной список и (как упомянул Уилл Несс) детерминированный c целое число позиция . Функция списка splitAt :: Int -> [a] -> ([a], [a]) может пригодиться здесь. Например: 

funcShuffleList :: Int -> [a] -> [a]
funcShuffleList _ [] = []
funcShuffleList pos ls =
    if (pos <=0) || (length(take (pos+1) ls) < (pos+1))
      then ls -- pos is zero or out of bounds, so leave list unchanged
      else let (left,right) = splitAt pos ls
           in  (head right) : (left ++ (tail right))

Тестирование: 

 λ> 
 λ> funcShuffleList  4  [0,1,2,3,4,5,6,7,8,9]
 [4,0,1,2,3,5,6,7,8,9]
 λ> 
 λ> funcShuffleList 5 "@ABCDEFGH"
 "E@ABCDFGH"
 λ>

Как только вы это получите, вы можете ввести вопросы случайности проще. И вам не нужно явно привлекать IO, как это делает любая монада, дружественная к случайности: 

shuffleList :: MonadRandom mr => [a] -> mr [a]
shuffleList [] = return []
shuffleList ls =
    do
       let maxPos = (length ls) - 1
       pos <- getRandomR (0, maxPos)
       return (funcShuffleList pos ls)

... IO - это всего лишь один экземпляр MonadRandom .

Вы можете запустить код с помощью генератора случайных чисел по умолчанию, размещенного в IO: 

main = do
    let inpList = [0,1,2,3,4,5,6,7,8]::[Integer]

    putStrLn $ "inpList  = " ++ (show inpList)

    -- mr automatically instantiated to IO:
    outList1 <- shuffleList inpList
    putStrLn $ "outList1 = " ++ (show outList1)
    outList2 <- shuffleList outList1
    putStrLn $ "outList2 = " ++ (show outList2)

Вывод программы: 

$ pickShuffle
inpList  = [0,1,2,3,4,5,6,7,8]
outList1 = [6,0,1,2,3,4,5,7,8]
outList2 = [8,6,0,1,2,3,4,5,7]
$ 
$ pickShuffle
inpList  = [0,1,2,3,4,5,6,7,8]
outList1 = [4,0,1,2,3,5,6,7,8]
outList2 = [2,4,0,1,3,5,6,7,8]
$

Вывод здесь не воспроизводится, так как генератор по умолчанию засеян по времени запуска в наносекундах.

Если вам нужна полная случайная перестановка, вы можете посмотреть здесь и там - алгоритм Кнута или Фишера-Йейтса .

...