从数组或列表中随机选取元素

Question

免责声明：我使用的是 PureScript，但还添加了 Haskell 标签，因为我认为这在两种语言中的行为方式可能相同，而且 Haskell 社区更大.

我想从数组中随机选取一个元素，重复。每次我都期待一个新的随机选择，但重复调用的值总是相同的。随机函数似乎只在每个运行程序中计算一次。

这在后续调用中总是 returns 相同的名称：

import Data.Array (length, unsafeIndex)
import Effect.Random (randomInt)
import Effect.Unsafe (unsafePerformEffect)
import Partial.Unsafe (unsafePartial)

pick :: forall a. Array a -> a
pick arr = unsafePartial $ unsafeIndex arr i where
    i = unsafePerformEffect $ randomInt 0 (length arr - 1)

name :: String
name = pick names

使用此变通方法，它每次 returns 一个新的随机选择：

import Data.Array (length, unsafeIndex)
import Effect.Random (randomInt)
import Effect.Unsafe (unsafePerformEffect)
import Partial.Unsafe (unsafePartial)

pick :: forall a. Array a -> a
pick arr = unsafePartial $ unsafeIndex arr i where
    i = unsafePerformEffect $ randomInt 0 (length arr - 1)

-- without the dummy argument, this is not re-evaluated
-- on subsequent calls and always returns the same name
name :: Unit -> String
name _ = pick names

我正在使用 Data.Array, Effect.Random, Effect.Unsafe and Partial.Unsafe。

我觉得这是一个丑陋的 hack。实现这一目标的正确方法是什么？

Answer 1

一个每次调用时都会做不同事情的函数与 Haskell 的设计相反，我认为 PureScript 也是如此，基于您必须导入的名称 "Effect.Unsafe" .如果不使用 Unsafe 包中的东西 "cheating" 就不可能编写这样的函数，任何与这样的函数交互的人都会头疼。

相反，为您的函数提供更诚实的类型签名。我不知道 PureScript 的等价物，但在 Haskell 中它会是这样的（改编自 Get a random list item in Haskell）：

pick :: [a] -> Maybe (IO a)
pick [] = Nothing
pick xs = Just $ do
  i <- randomRIO (0, len)
  pure $ xs !! i
  where len = length xs - 1

首先，您承认如果给定一个空列表，该函数实际上无法从列表中生成一个项目¹。然后，您承认这不是一个纯函数：您必须执行 IO（也许 PureScript 称之为 Effect？）来随机选择。现在调用者知道这两种影响，并且必须处理它们：通过检查是否为空并将其视为 IO 操作而不是纯值。

¹ 正如 Parse, don't validate 所说，让您的函数接受 NonEmpty a 而不是接受 [a] 并返回实际上会更好a Maybe，但我不想在这里引入新的依赖。

Answer 2

您可能希望将“随机”标签附加到您的问题。

我不知道 PureScript，对于新手来说文档似乎很少，但在 Haskell 圈子里，这似乎是一个相当普遍的抱怨：随机数生成函数 . The usual jokes 关于应用随机数。

但是，Haskell 有一个关于随机数生成的既定原则。这不一定涉及 IO，即使在 Haskell 中，IO monad 恰好“托管”了一个随机数生成器。

在 Haskell 中，您需要：

import  System.Random
import  Control.Monad.Random

问题是一个函数，给定相同的参数，总是returns相同的结果。

解决方案是您需要将随机数生成器的初始状态作为函数参数包含在内，并将更新后的新状态作为结果的一部分返回。这就是 Haskell 函数 randomR :: RandomGen g => (a, a) -> g -> (a, g) 所做的。第一个参数是输出范围。如果您的数组有 100 个索引在 0 到 99 之间的元素，那将是一个 2 元组：(0,99).

一旦你有一个返回单个随机值的函数，你就可以轻松地构建第二个返回任意数量的值的函数，例如：

randomRn :: (RandomGen g, Random a) => (a, a) -> Int -> g -> ([a], g) 
randomRn range count g0 =
    if (count <= 0)
       then  ([], g0)  -- no values and no change
       else  let (a0, g1) = randomR  range g0
                 (as, gf) = randomRn range (count-1) g1  -- recursive call
             in
               (a0:as, gf)

您可以使用您的函数：

main = do
    let  seed          = 4242
         g0            = mkStdGen seed  -- get a generator
         arraySize     = 100::Int
         range         = (0, arraySize-1)
         count         = 20  -- want "count" random indexes into array
         (indexes, gf) = randomRn range count g0

    putStrLn $ "Random indexes v1: " ++ show indexes

程序输出：

Random indexes v1: [9,56,13,9,38,86,62,18,77,4,66,65,27,33,68,55,94,15,77,45]

现在，根据品味、风格和问题的复杂性，您可能会发现状态的显式存在很烦人，并想以某种方式隐藏它。为此，Haskell 使用状态 monad 的变体，称为 MonadRandom。使用这种方法，您将使用这样的代码来定义一个 monadic 操作 返回一个随机值列表：

iterateMn :: MonadRandom mr => (Int, Int) -> Int -> mr [Int]
iterateMn range count =
    if  (count <= 0)  then
        return []  -- no action required
    else
        do
            v1 <- getRandomR range
            vs <- iterateMn range (count-1)
            return (v1:vs)

除了您没有显式管理状态外，这与上面的代码基本相同。 action 就是运行那样，使用函数 runRand:

    let action          = iterateMn range count    -- monadic action object
        (indexes2, gf2) = runRand action g0        -- go generate indexes

此处有更多详细信息：

PureScript 随机数生成工具似乎是在 Javascript 工具之上构建的。根据您的要求有多严格，它可能不够好，也可能不够好。您可能决定硬着头皮实施，例如，随机数生成器的 PureScript 版本 MRG32k3A。众所周知，它的统计特性非常强大，而且它的状态具有非常小的内存大小，因此非常适合函数式编程语言。显然已经有几个 Lisp 实现可用。

Answer 3

感谢@amalloy 的回答，我找到了我认为对我的案例来说很好的解决方案。

关键是保持来自随机数生成的Effect（Effect对应Haskell中的IO ) 而不是用 unsafePerformEffect 丢弃它 。 Effect 反映了一个事实，即在该值的计算中涉及一些副作用，并且每次都可能有不同的结果。这正是我想要的。所以有了这个新的类型签名，它现在的行为符合我的预期：name :: Effect String。每次效果为"run"，从数组中随机选择一个新字符串

正如@amalloy 所建议的，我现在也使用 NonEmptyArray。

pick :: forall a. NonEmptyArray a -> Effect a
pick arr = do
    i <- randomInt 0 (length arr - 1)
    let item = arr !! i
    case item of
        Just one -> pure one
        Nothing -> pure $ head arr
        -- still have to handle the Maybe from (!!) which is
        -- a bit annoying since this obviously can never be Nothing

name :: Effect String
name = pick names

main :: Effect Unit
main = do
    name >>= log
    name >>= log
    name >>= log
    -- new pick each time

从数组或列表中随机选取元素

Picking random elements from an array or a list

random

purescript