Выбор случайных элементов из массива или списка - PullRequest
Новая
       53

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

0 голосов
/ 01 апреля 2020

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

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

Всегда возвращает одно и то же имя при последующих вызовах: 

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

С этим обходным решением каждый новый случайный выбор возвращается время: 

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 и Partial. Небезопасно .

Мне кажется, что это безобразный хак. Как правильно достичь этого?

Ответы [ 3 ]

6 голосов
/ 01 апреля 2020

Функция, которая делает что-то другое каждый раз, когда вы вызываете ее, отличается от дизайна Haskell, и я предполагаю также PureScript, основанный на названии "Effect.Unsafe", которое вам пришлось импортировать. Невозможно написать такую ​​функцию без «мошенничества», используя что-то из небезопасного пакета, и у любого, кто взаимодействует с такой функцией, будет головная боль.

Вместо этого дайте вашей функции более честную сигнатуру типа. Я не знаю PureScript-эквивалент, но в Haskell это было бы что-то вроде этого (адаптировано из Получить случайный элемент списка в Haskell): 

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

First , вы признаете, что если дан пустой список, функция не может фактически создать элемент из списка 1 . Затем вы признаете, что это не чистая функция: вы должны выполнить IO (может PureScript называет это Эффектом?), Чтобы выбрать случайным образом. Теперь вызывающие абоненты знают обо всех этих эффектах и ​​должны обрабатывать их: проверяя на пустоту и рассматривая это как действие ввода-вывода, а не как чистое значение.

1 Как Анализирует, не проверяет утверждает, что на самом деле было бы лучше, если бы ваша функция принимала NonEmpty a вместо [a] и возвращала Maybe, но я не хотел вводить здесь новые зависимости .

1 голос
/ 01 апреля 2020

Благодаря ответу @amalloy я нашел то, что я считаю хорошим решением для моего случая.

Ключом было сохранить Effect от генерации случайных чисел ( Effect соответствует IO в Haskell) вместо его отбрасывания с unsafePerformEffect. Effect отражает тот факт, что при вычислении этого значения участвует некоторый побочный эффект, и каждый раз он может давать разные результаты. Это именно то, что я хочу. Так что с этой новой сигнатурой типа она теперь ведет себя как я ожидал: name :: Effect String. Каждый раз, когда эффект «запускается», он случайным образом выбирает новую строку из массива.

Теперь я также использую NonEmptyArray, как и предложил @amalloy. 

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
0 голосов
/ 01 апреля 2020

Возможно, вы захотите прикрепить «случайный» тег к вашему вопросу.

Я не знаю о PureScript, и документация кажется новичку скудной, но в кругах Haskell кажется, что довольно распространенная жалоба: функция генерации случайных чисел всегда возвращает одно и то же значение . Применяются обычные анекдоты о случайных числах.

Однако Haskell имеет установленный doctrine относительно генерации случайных чисел. Это необязательно требует ввода-вывода, даже если в Haskell монада ввода-вывода «содержит» генератор случайных чисел.

В Haskell вам потребуется: 

import  System.Random
import  Control.Monad.Random

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

Решение состоит в том, что в качестве аргумента функции необходимо включить начальное состояние генератора случайных чисел, а новый обновленное состояние возвращается как часть результата. Это то, что делает Haskell function randomR :: RandomGen g => (a, a) -> g -> (a, g) . Первый аргумент - это выходной диапазон. Если в вашем массиве 100 элементов с индексами от 0 до 99, это будет двойной кортеж: (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 использует вариант монады состояний, известный как MonadRandom . Используя такой подход, вы могли бы использовать такой код для определения monadi c action , возвращающего список случайных значений: 

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

Подробнее здесь: SO_q57890878_r11282404

It кажется, что средство генерации случайных чисел PureScript построено на базе Javascript. В зависимости от того, насколько строгими являются ваши требования, это может быть или не быть достаточно хорошим. Вы можете решить прикусить пулю и внедрить, например, PureScript-версию генератора случайных чисел MRG32k3A . Известно, что его статистические свойства достаточно сильны, а его состояние имеет очень маленький объем памяти и, таким образом, аккуратно адаптируется к функциональным языкам программирования. По-видимому, уже есть несколько реализаций Lisp.

...