чистый Кнут / Фишер-Йейтс перетасовать в хаскеле - PullRequest
Новая
       33

чистый Кнут / Фишер-Йейтс перетасовать в хаскеле

2 голосов
/ 19 июня 2019

На ходу я мог бы написать такую ​​функцию: 

func pureFisherYates(s []int, swaps []int) []int {
    newS := copy(s)
    for i, _ := range newS {
            for _, j := range swaps {
                    newS[i], newS[j] = newS[j], newS[i]
            }
    }
}

Мне это кажется чистой функцией.Он всегда возвращает один и тот же вывод при одном и том же входном сигнале и не изменяет состояние мира (кроме как в некотором строгом смысле, как это делает любая другая функция, занимая ресурсы процессора, создавая тепловую энергию и т. Д.).Тем не менее, всякий раз, когда я ищу, как сделать чистое перетасовывание, я нахожу что-то вроде this , и всякий раз, когда я ищу специально Fash-Yates реализации на Haskell, я либо получаю 0^2 Fisher-Yates, реализованный с помощью списка, либо [a] -> IO [a] реализация.Существует ли [a] -> [a] O(n) shuffle и если нет, то почему моя вышеприведенная реализация нечиста.

1 Ответ

7 голосов
/ 19 июня 2019

Монада ST допускает именно такую ​​инкапсулированную изменчивость, а Data.Array.ST содержит массивы, которые могут быть изменены в ST, а затем неизменную версию, возвращаемую наружу.

https://wiki.haskell.org/Random_shuffle дает две реализации тасования Фишера-Йейтса с использованием ST.Они не буквально [a] -> [a], но это потому, что генерация случайных чисел также должна быть обработана: 

import System.Random
import Data.Array.ST
import Control.Monad
import Control.Monad.ST
import Data.STRef

-- | Randomly shuffle a list without the IO Monad
--   /O(N)/
shuffle' :: [a] -> StdGen -> ([a],StdGen)
shuffle' xs gen = runST (do
        g <- newSTRef gen
        let randomRST lohi = do
              (a,s') <- liftM (randomR lohi) (readSTRef g)
              writeSTRef g s'
              return a
        ar <- newArray n xs
        xs' <- forM [1..n] $ \i -> do
                j <- randomRST (i,n)
                vi <- readArray ar i
                vj <- readArray ar j
                writeArray ar j vi
                return vj
        gen' <- readSTRef g
        return (xs',gen'))
  where
    n = length xs
    newArray :: Int -> [a] -> ST s (STArray s Int a)
    newArray n xs =  newListArray (1,n) xs

и 

import Control.Monad
import Control.Monad.ST
import Control.Monad.Random
import System.Random
import Data.Array.ST
import GHC.Arr

shuffle :: RandomGen g => [a] -> Rand g [a]
shuffle xs = do
    let l = length xs
    rands <- forM [0..(l-2)] $ \i -> getRandomR (i, l-1)
    let ar = runSTArray $ do
        ar <- thawSTArray $ listArray (0, l-1) xs
        forM_ (zip [0..] rands) $ \(i, j) -> do
            vi <- readSTArray ar i
            vj <- readSTArray ar j
            writeSTArray ar j vi
            writeSTArray ar i vj
        return ar
    return (elems ar)

*Main> evalRandIO (shuffle [1..10])
[6,5,1,7,10,4,9,2,8,3]

РЕДАКТИРОВАТЬ: с фиксированным аргументом swapsкак и в вашем коде Go, код довольно прост 

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Array.ST
import Data.Foldable
import Control.Monad.ST

shuffle :: forall a. [a] -> [Int] -> [a]
shuffle xs swaps = runST $ do
    let n = length xs
    ar <- newListArray (1,n) xs :: ST s (STArray s Int a)
    for_ [1..n] $ \i ->
        for_ swaps $ \j -> do
            vi <- readArray ar i
            vj <- readArray ar j
            writeArray ar j vi
            writeArray ar i vj
    getElems ar

, но я не уверен, что вы можете разумно назвать его Shuffle Фишера-Йейтса.

...