26

[1, 2, 3]ヒットするまで、一連の数字 ( ) から置換なしでサンプリングするにはどうすればよいxですか? 私の計画は、リストをシャッフルして[1, 2, 3]切り刻むことでしたx:

-- chopAt 3 [2, 3, 1] == [2, 3]
-- chopAt 3 [2, 1, 3] == [2, 1, 3]
-- chopAt 3 [3, 1, 2] == [3]
chopAt _ [] = []
chopAt x (y:ys)
  | x /= y    = y : chopAt x ys
  | otherwise = [y]

しかし、私はリストをシャッフルする方法を理解できませんでした (またはモナドをまだ理解していません)。

-- sample without replacement from [1, 2, 3] until one hits a 3
-- x <- shuffle [1, 2, 3]
-- print (chopAt 3 x)
main = do
-- shuffle [1, 2, 3]
  print (chopAt 3 [1, 3, 2])
4

6 に答える 6

50

シャッフルを実装するには、randomを使用し、 MonadRandomを使用することもできます。ここにいくつかの良い答えがあります

しかし、それは実際に運用されています。これが舞台裏で起こっていることです。

私。

ランダム性は、Haskell で最初に遭遇し、不純物を処理しなければならない場所の 1 つです。シャッフルとサンプルは非常に単純に見え、物理的な画面への出力や印刷にまとめられるべきではないように思われるため、不快に思えます。核兵器を発射しますが、多くの場合purity == referentially transparent、参照的に透明なランダム性は役に立たないでしょう.

random = 9 -- a referentially transparent random number

したがって、ランダム性を純粋にするためには、ランダム性について別の考え方が必要です。

Ⅱ．

再現性を高めるために使用される科学的コードの典型的な「チート」 (非常に重要) は、実験のランダムシードを修正して、コードを実行するたびにまったく同じ結果が得られることを他の人が検証できるようにすることです。これこそまさに参照透過性です！試してみよう。

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

ここmersenneTwisterPerturbで、 はSeeds から への疑似乱数マッピングでIntあり、は s からs へのsplitSeed疑似乱数マッピングです。これらの関数は両方とも完全に決定論的 (かつ参照透過的) であることに注意してください。SeedSeedrandom

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 (head rest) : shuffle' is (firsts ++ tail 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])

しかし、厄介なことに気付くでしょう:異なるランダム順列を作成したい場合は、gen を変化させ続ける必要があります。

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 f :: Seed -> (a, Seed)はかなり一般的な結果です。名前を付けましょう

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

Seedで意味のあるs を作成できることがわかっているので、型を次IOのように変換する明らかな関数があります。RandomIO

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

そして今、何か役に立つものを手に入れたような気がします--- type のランダムな値の概念は、a後の値がすべて同一にならないように次を返す s のRandom a単なる関数です。ランダムな値を構成し、これを自動的に渡す機械を作成することもできますSeedSeedRandomSeed

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

でも、ただ捨てるだけなので、それは少しばかげています_aValue。2 番目の乱数が実際には最初の乱数値に実質的に依存するように、それらを構成しましょう。

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

Ⅵ．

そして、これは私が書いてきた問題全体の核心になります。ランダム性は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また、モナド準同型を空想的に呼び出すこともできますが、それはまったく別のトピックです。

ということで、まとめますと

  1. 参照透過性言語のランダム性にはSeedsが必要
  2. カートSeedは迷惑です
  3. Seeds を自然にルーティングするランダム値の「リフティング」および「バインド」には、共通のパターンがあります。
  4. そのパターンはモナドを形成します

そして、本当に短い答えは、あなたはおそらく乱数を使いたいと思うでしょう。それらは、一般的に「サンプリング」に役立ちます。

乾杯！

于 2013-02-04T18:40:45.173 に答える
4

順列をお探しですか？

また、cropAt経由で実装できるようtakeWhileです。個人的には、手作りよりも標準的なコンビネーターの方が好きです。

于 2013-02-04T17:41:15.583 に答える
2

誰もが、ある時点または別の時点でこれに遭遇したようです。これは問題に対する私の簡単な解決策です： 

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
于 2015-03-14T21:47:03.740 に答える
2

私の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)
于 2013-02-05T13:16:26.833 に答える