Как перемешать список?

Ответ 1

Используйте random и, возможно, даже MonadRandom для осуществления ваших тасований. Несколько хороших ответов существуют здесь

Но это действительно работает. Вот что происходит за кулисами.

I.

Случайность - одно из первых мест в Haskell, с которым вы сталкиваетесь и должны обрабатывать нечистоту, - что кажется оскорбительным, потому что тасования и образцы кажутся такими простыми и не чувствуют, что они должны быть в комплекте с печатью на физический экран или запускающее ядерное оружие, но часто purity == referentially transparent и ссылочно прозрачная случайность бесполезно.

random = 9 -- a referentially transparent random number

Итак, нам нужна другая идея о случайности, чтобы сделать ее чистой.

II.

Типичный "чит" в научном коде, который используется для повышения воспроизводимости - супер важно, - это исправить случайное семя эксперимента, чтобы другие могли убедиться, что они получают одинаковые результаты каждый раз, когда ваш код запущен. Это точно ссылочная прозрачность! Попробуем это.

type Seed = Int
random :: Seed -> (Int, Seed)
random s = (mersenneTwisterPerturb s, splitSeed s)

где mersenneTwisterPerturb - псевдослучайное отображение от Seed до Int, а splitSeed - псевдослучайное отображение от Seed до Seed s. Обратите внимание, что обе эти функции полностью детерминированы (и ссылочно прозрачны), поэтому random также, но мы можем создать бесконечный ленивый псевдослучайный поток, подобный этому

randomStream :: Seed -> [Int]
randomStram s = mersenneTwisterPerturb s : randomStream (splitSeed s)

Опять же, этот поток детерминирован на основе значения Seed, но наблюдатель, который видит только поток, а не семя, не может предсказать его будущие значения.

III.

Можно ли перетасовать список, используя случайный поток целых чисел? Конечно, мы можем, используя модульную арифметику.

shuffle' :: [Int] -> [a] -> [a]
shuffle' (i:is) xs = let (firsts, rest) = splitAt (i `mod` length xs) xs
                     in (last firsts) : shuffle is (init firsts ++ rest)

Или, чтобы сделать его более самодостаточным, мы можем предварительно создать функцию генерации потока, чтобы получить

shuffle :: Seed -> [a] -> [a]
shuffle s xs = shuffle' (randomStream s) xs

другое "затраченное семя" референциально прозрачная "случайная" функция.

IV.

Таким образом, это, кажется, повторяющаяся тенденция. Фактически, если вы просматриваете модуль System.Random, вы увидите множество функций, подобных тому, что мы написали выше (я специализировал некоторые классы типов)

random :: (Random a) => StdGen -> (a, StdGen)
randoms :: (Random a) => StdGen -> [a]

где random - тип типа вещей, которые могут быть сгенерированы случайным образом, а StdGen - это вид Seed. Это уже достаточный фактический рабочий код для записи необходимой функции перетасовки.

shuffle :: StdGen -> [a] -> [a]
shuffle g xs = shuffle' (randoms g) xs

и существует функция IO newStdGen :: IO StdGen, которая позволит нам построить случайное семя.

main = do gen <- newStdGen
          return (shuffle gen [1,2,3,4,5])

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

main = do gen1 <- newStdGen
          shuffle gen1 [1,2,3,4,5]
          gen2 <- newStdGen
          shuffle gen2 [1,2,3,4,5]

          -- using `split :: StdGen -> (StdGen, StdGen)`
          gen3 <- newStdGen
          let (_, gen4) = split gen3
          shuffle gen3 [1,2,3,4,5]
          let (_, gen5) = split gen4
          shuffle gen4 [1,2,3,4,5]

Это означает, что вам нужно будет делать много бухгалтерии StdGen или оставаться в IO, если вам нужны разные случайные числа. Это "имеет смысл" из-за ссылочной прозрачности снова - набор случайных чисел должен быть случайным по отношению друг к другу, поэтому вам нужно передавать информацию от каждого случайного события дальше к следующему.

Это действительно раздражает. Можем ли мы лучше?

V.

Ну, в общем, нам нужно, чтобы функция выполняла случайное семя, затем выводила некоторый "рандомизированный" результат и следующее семя.

withSeed :: (Seed -> a) -> Seed -> (a, Seed)
withSeed f s = (f s, splitSeed s)

Тип результата withSeed s :: Seed -> (a, Seed) является довольно общим результатом. Пусть дайте ему имя

newtype Random a = Random (Seed -> (a, Seed))

И мы знаем, что мы можем создавать значащие Seed в IO, поэтому существует очевидная функция для преобразования типов random в IO

runRandom :: Random a -> IO a
runRandom (Random f) = do seed <- newSeed
                          let (result, _) = f seed
                          return result

И теперь кажется, что у нас есть что-то полезное --- понятие случайного значения типа a, Random a - это просто функция на Seed, которая возвращает следующий Seed, чтобы позже Значения random не будут одинаковыми. Мы можем даже сделать некоторые машины для создания случайных значений и сделать это Seed -passing автоматически

sequenceRandom :: Random a -> Random b -> Random b
sequenceRandom (Random fa) (Random fb) = 
    Random $ \seed -> let (_aValue, newSeed) = fa seed in fb newSeed

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

bindRandom :: Random a -> (a -> Random b) -> Random b
bindRandom (Random fa) getRb = 
    Random $ \seed -> let (aValue, newSeed) = fa seed
                          (Random fb)       = getRb aValue
                      in fb newSeed

Мы также должны отметить, что мы можем делать "чистые" вещи до значений random, например, умножая случайное число на 2:

randomTimesTwo :: Random Int -> Random Int
randomTimesTwo (Random f) = Random $ \seed -> let (value, newSeed) = f seed
                                              in (value*2, newSeed)

который мы можем абстрагироваться как экземпляр Functor

instance Functor Random where
  fmap f (Random step) = Random $ \seed -> let (value, newSeed) = step seed
                                           in (f value, newSeed)

и теперь мы можем создавать интересные случайные эффекты, такие как броуновское движение

brownianMotion :: Random [Int]
brownianMotion = 
   bindRandom random $ \x -> 
       fmap (\rest -> x : map (+x) rest) brownianMotion

VI.

И это доходит до сути всего, о чем я писал. Случайность может существовать в монаде IO отлично, но она также может существовать сама по себе как более простая монада random. Мы можем сразу написать экземпляр.

instance Monad Random where
  return x = Random (\seed -> (x, seed))
  rx >>= f = bindRandom rx f

И так как это монада, мы получаем бесплатную нотацию do

brownianMotion' = do x <- random
                     rest <- brownianMotion'
                     return $ x : map (+x) rest

и вы даже можете получить фантазию и назвать runRandom монадным гомоморфизмом, но это совсем другая тема.

Итак, чтобы повторить

• Случайность в ссылочно прозрачном языке нуждается в Seed s
• carting Seed раздражает
• существует общий шаблон для "подъема" и "привязки" случайных значений, который направляет Seed вокруг естественного
• этот шаблон образует монаду

И действительно короткий ответ заключается в том, что вы, вероятно, захотите использовать random и, возможно, даже MonadRandom, чтобы реализовать ваши тасования. Они будут полезны для "отбора проб" в целом.

Ура!

Ответ 2

Вы ищете permutations?

Также кажется, что cropAt может быть реализовано через takeWhile. Я лично предпочитаю стандартные комбинаторы над ручным.

Ответ 3

Ниже вы можете найти какое-то простое решение с начала обучения в Haskell. Если говорить правду, я все еще в начале или чуть-чуть позади; -)

import System.Random
import Control.Applicative

shuffle :: [a] -> IO [a]
shuffle [] = return []
shuffle lst = do
    (e, rest) <- pickElem <$> getIx
    (e:) <$> shuffle rest
    where
    getIx = getStdRandom $ randomR (1, length lst)
    pickElem n = case splitAt n lst of
        ([], s) -> error $ "failed at index " ++ show n -- should never match
        (r, s)  -> (last r, init r ++ s)

Ответ 4

Кажется, что каждый сталкивался с этим в какой-то момент времени. Это мое быстрое решение проблемы:

import System.Random

shuffle :: [a] -> IO [a]
shuffle [] = return []
shuffle xs = do randomPosition <- getStdRandom (randomR (0, length xs - 1))
                let (left, (a:right)) = splitAt randomPosition xs
                fmap (a:) (shuffle (left ++ right))

Обратите внимание, что сложность O (N ^ 2), поэтому это довольно неэффективно для больших списков. Другой способ - реализовать Fisher-Yates shuffle с помощью изменяемых массивов (линейная сложность):

import Data.Array.IO
import System.Random

swapElements_ :: (MArray a e m, Ix i) => a i e -> i -> i -> m ()
swapElements_ arr i j = do a <- readArray arr i
                           b <- readArray arr j
                           writeArray arr i b
                           writeArray arr j a
                           return ()

shuffle :: [a] -> IO [a]
shuffle xs = do let upperBound = length xs
                arr <- (newListArray (1, upperBound) :: [a] -> IO (IOArray Int a)) xs
                mapM_ (shuffleCycle arr) [2..upperBound]
                getElems arr
  where shuffleCycle arr i = do j <- getStdRandom (randomR (1, i))
                                swapElements_ arr i j

Ответ 5

Для перемешивания списка используйте библиотеку random-shuffle:

import System.Random (newStdGen)
import System.Random.Shuffle (shuffle')

main = do
  rng <- newStdGen

  let xs = [1,2,3,4,5]

  putStrLn . show $ shuffle' xs (length xs) rng