如何改变名单？

Question

如何在没有替换的情况下从一组数字([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]

但是我无法弄清楚如何改变列表(或者了解Monads).

-- 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])

Answer 1

使用随机甚至MonadRandom来实现您的随机播放.这里有一些好的答案

但这确实可以运作.这是幕后发生的事情.

一世.

随机性是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是从伪随机映射Seeds到Int和splitSeed是伪随机映射从Seeds到Seed秒.请注意,这两个函数都是完全确定的(并且引用透明),所以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))

我们知道我们可以创建有意义的Seeds in IO,因此有一个明显的函数可以将Random类型转换为IO

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

而现在感觉我们已经有了一些有用的东西 - 一个随机值类型的概念a,Random a它只是Seeds 上的一个函数,它返回下一个值,Seed以便后面的Random值不会全部相同.我们甚至可以制作一些机器来组合随机值并Seed自动执行此操作

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很好地存在于monad中,但它也可以作为一个更简单的Randommonad存在.我们可以立即编写实例.

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

因为它是一个monad,我们得到自由的do表示法

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

你甚至可以得到幻想并称之为runRandommonad同态,但这是一个非常不同的话题.

所以,回顾一下

1. 在引用透明语言中的随机性需要Seeds
2. 卡车Seed是很烦人的
3. 有一种常见的模式来"提升"和"绑定"随机值,这些随机值Seed会自然地绕过s
4. 这种模式形成了一个单子

而真正简短的回答是你可能想要随机使用甚至MonadRandom来实现你的随机播放.它们通常会为"抽样"派上用场.

干杯!

Answer 2

要打乱列表，请使用random-shuffle库：

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

main = do
  rng <- newStdGen

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

  print $ shuffle' xs (length xs) rng