Рекурсивное определение списка монадических случайных чисел: самый идиоматический Haskell и аналог чистого кода

Question

Я пытаюсь рекурсивно составить список случайных чисел, который использует предыдущее значение, чтобы получить следующее (поэтому рекурсия требуется вместо карты или сгиба, а также я предпочитаю делать это явным, если map / foldr не делает это смехотворно простымв сравнении).

Использование чистого PRNG, на мой взгляд, очень просто и идиоматично (puregaussian использует System.Random для генерации нормального варианта и имеет тип puregaussian :: System.Random.RandomGen t => t -> Double -> Double -> (Double, t)).

purecurse :: System.Random.RandomGen t => t -> Double -> [Double] -> [Double]
purecurse gen current [] = []
purecurse gen current (x:xs) = let (rand, gen2) = puregaussian gen 0 1
                                   next = current + rand
                               in current:purecurse gen2 next xs

К сожалению, чистые PRNG, кажется, не так хорошо развиты в Haskell, как монадические, поэтому я хочу сделать то же самое, используя библиотеку, такую ​​как random-fu или mwc-вероятность, и решения, которые я нашел для работы,либо unidiomatic, не такой краткий, или оба.

Вот решение, использующее нотацию do, которая работает, и почему меня это не устраивает:

import Control.Monad.Primitive
import System.Random.MWC.Probability

recurse :: PrimMonad m => Gen (PrimState m) -> [Double] -> [Double] -> m [Double]
recurse gen history@(current:_) [] = return history
recurse gen history@(current:_) (x:xs) = do
                                         rand <- (sample (normal 0 1) gen)
                                         let next = current + rand
                                         recurse gen (next:history) xs

Прежде всего, я бы предпочелиспользуйте >>=, чем обозначения, но я не смог найти способ связать переменную rand с типом m Double, а затем поднять ее, чтобы получить m [Double] в конце дело.Похоже, не так много документации (которую я мог бы найти) или примеров того, как сделать что-то подобное.Я подумал, что, возможно, будет необходимо вложить операторы (>>=), но это может сделать функцию чрезвычайно сложной или нечитаемой.Если это компромисс, может быть, нотация просто чище, но мне не удалось справиться даже с этой работой, и я хотел бы узнать, как это сделать.

Во-вторых, функция требует передачи всего списка.при каждом вызове и возвращает список обратно (и просто переключая next и history нарушает его).

Итак.Я хотел бы иметь возможность передать начальное состояние и список для рекурсии, который возвращает монадический список значений.

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

Answer 1

Кажется, ваша проблема связана с do-нотацией и монадой. Вы предполагаете, что происходит гораздо больше магии, чем на самом деле: изучение того, как работает десугаринг поможет вам здесь.

В любом случае, давайте попробуем преобразовать немонадную версию в монадическую поэтапно. Сначала подпись типа:

recurse :: PrimMonad m => Gen (PrimState m) -> Double -> [Double] -> m [Double]

Я не уверен, почему вы указали [Double] в качестве второго параметра в вашей версии: мы хотим как можно меньше отличаться от оригинала. Первый пункт, затем:

purecurse gen current [] = []
-- Goes to:
recurse gen current [] = return []

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

purecurse gen current (x:xs) = let (rand, gen2) = puregaussian gen 0 1
                                   next = current + rand
-- Goes to:
recurse gen current (x:xs) = do rand <- (sample (normal 0 1) gen)
                                let next = current + rand

Но последний сбил вас с толку. В идеале мы бы написали:

in current:purecurse gen2 next xs
-- Goes to:
current:recurse gen next xs

Но это не работает! Более того, вы получаете запутанную ошибку:

• Couldn't match type ‘Double’ with ‘[Double]’
  Expected type: m [Double]
    Actual type: [Double]

Вероятно, именно это привело вас на неверный путь. Эта проблема не имеет ничего общего со списками: она связана с m (инкапсулирующей монадой). Когда вы пишете current : xs, xs должен быть списком: в этом примере это на самом деле m [Double], или список, заключенный в монаду. Есть два способа решения проблемы (оба они эквивалентны). Мы можем развернуть список, снова используя do dotation:

rest <- recurse gen next xs
return (current : rest)

Или мы могли бы поднять функцию current : для работы внутри монады:

fmap (current:) (recurse gen next xs)

Answer 2

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

Я не уверен, что делает purecurse, но это можно записать как

import           Streaming
import qualified Streaming.Prelude as S

recurse :: PrimMonad m 
        => Gen (PrimState m) 
        -> Double 
        -> [Double] 
        -> Stream (Of Double) m ()
recurse gen current [] = 
    return ()
recurse gen current (x:xs) =
    S.yield current *> -- (*>) and (>>) work like concatenation for pure lists
    lift (sample (normal 0 1) gen) >>= \rand -> 
    recurse gen (current + rand) xs

Или, более естественно, используя do-обозначения, как:

recurse :: PrimMonad m 
        => Gen (PrimState m) 
        -> Double 
        -> [Double] 
        -> Stream (Of Double) m ()
recurse gen current [] = 
    return ()
recurse gen current (x:xs) = 
    do S.yield current -- (*>) and (>>) work like concatenation for pure lists
       rand <- lift $ sample (normal 0 1) gen
       recurse gen (current + rand) xs

Теперь вы можете использовать такую ​​функцию, как S.take, чтобы генерировать / извлекать только части результата. Если вы хотите получить весь список, вы можете использовать S.toList_.

Answer 3

есть ли на Хаскеле идиоматический способ написания такой рекурсии монадические значения, приводящие к монадическому списку, который похож на структура чистой функции

Обычно, когда необходимо применить монадические значения к чистой функции, Аппликативный оператор , такой как <$>, <*>, может быть полезен.

В частности, для построения списка часто применяется оператор (:) рекурсивным способом для построения списка, например

f [] = []
f (x:xs) = x : f xs

префиксным способом:

(:) x (f xs)

Однако (:) - это чистая функция, по умолчанию она не принимает монадическое значение, но хорошая новость заключается в том, что каждый тип данных, который является экземпляром Monad, также является экземпляром Applicative. с помощью упомянутого выше оператора Applicative монадическое значение может быть применено к чистой функции без каких-либо изменений. Например,

(:) <$> (pure x) <*> (pure .f) xs

вернет монадический список вместо чистого списка.

Возвращаясь к вашему вопросу, лично я думаю, что ваше решение уже почти идиоматический способ сделать это (так как оно простое и читаемое), за исключением того, что всегда добавляйте next random value в начале history.

Как вы сказали, the list back in reverse и хуже, когда список history уже имеет старое случайное значение, неудобно выяснять, что является новым добавлением к нему.

Чтобы решить эту проблему, его можно немного изменить:

recurse :: PrimMonad m => Gen (PrimState m) -> [Double] -> [Double] -> m [Double]
recurse gen history [] = return history
recurse gen history (x:xs) = do rand <- (sample (normal 0 1) gen)
                                let next = (last history) + rand
                                recurse gen (history ++ [next]) xs

Имеет смысл, если последний элемент истории является новейшим случайным значением.

Однако разница между (:) и (++): (:) - это O (1), а (++) - это O (N), где N - длина списка истории. (и last history также является O (N) вместо O (1)).

Чтобы заархивировать эффективное решение, может понадобиться вспомогательная функция, скажем, newHistory, для создания нового списка случайных значений в виде:

newHistory::PrimMonad m=>Gen(PrimState m)->m Double->[Double]->m [Double]
newHistory _ _ []             = return []
newHistory gen current (x:xs) = let next = (+) <$> current <*> sample (normal 0 1) gen
                                in  (:) <$> next <*> newHistory gen next xs

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

А затем добавить обратно к исходному списку history как:

(++) <$> pure history <*> newHistory gen (pure $ last history) xs

А соответствующая версия функции recurse выглядит следующим образом:

recurse2::PrimMonad m=>Gen(PrimState m)->[Double]->[Double]->m [Double]
recurse2 gen history xs = 
    (++) <$> pure history <*> newHistory gen (pure $ last history) xs

    where newHistory::PrimMonad m=>Gen(PrimState m)->m Double->[Double]->m [Double]
          newHistory _ _ []         = return []
          newHistory gen current (x:xs) = 
            let next = (+) <$> current <*> sample (normal 0 1) gen
            in  (:) <$> next <*> newHistory gen next xs

Answer 4

Главный вопрос, с которым я хотел бы помочь: есть ли идиоматический способ написания на Haskell такой рекурсии монадических значений, приводящий к монадическому списку, который похож на структуру чистой функции?

Вы можете сделать это в два этапа. Пусть ваша рекурсивная функция вернет список «монадических действий», а затем скомпонует / упорядочит эти действия.

Давайте рассмотрим более простую, но аналогичную функцию для удобства изложения. Вместо случайности давайте рассмотрим ввод. Список, к которому вы обращаетесь, предназначен только для размера (содержимое игнорируется), поэтому давайте просто используем целое число.

rc ::  Int -> [Double] -> IO [Double]
rc 0 h        = return h
rc n h@(cr:_) = do rand <- readLn :: IO Double
                   let nx = cr + rand
                   rc (n-1)(nx:h) 

Вот аналогичная альтернатива, которая работает так, как вы хотите

rc' ::  Int -> Double -> IO [Double]
rc' 0 cr = return []
rc' n cr = do rand <- readLn :: IO Double
              let nx = cr + rand
              xs   <- rc' (n-1) nx
              return (nx : xs)

А здесь без обозначений

rc'' ::  Int -> Double -> IO [Double]
rc'' 0 cr = return []
rc'' n cr = (readLn :: IO Double) >>= (\rand -> 
              let nx = cr + rand 
              in (rc'' (n-1) nx) >>= (\xs ->
                 return (nx : xs))) 

В любом случае, еще одна вещь, которую вы можете сделать, это абстрагировать отрывки кода, а не иметь монолитное представление.

На каждом шаге вам требуется текущее значение для генерации нового. Таким образом, шаг является функцией типа Double -> IO Double. И это довольно аккуратный тип, фундаментальный в мире монад. Вы можете привязать значения к шагу с помощью x >>= step или составить два шага с помощью step1 >=> step2. Итак, давайте пойдем с этим.

step :: Double -> IO Double
step cr = do rand <- readLn :: IO Double
             return (cr + rand)

Это очень легко понять. Вы «генерируете» число, добавляете текущий и возвращаете результат. И вы хотите сделать n таких шагов, поэтому составьте список шагов.

steps :: Int -> [Double -> IO Double]
steps n = replicate n step 

Теперь вы можете выбирать, как их комбинировать. Например, было бы очень естественно сложить список шагов с помощью >=>. Вы получите это,

runSteps :: Int -> Double -> IO Double 
runSteps n = foldr (>=>) return (steps n)

Это близко к тому, что вы хотите, но возвращает только конечный результат, а не накапливать сгенерированные значения на каждом шаге. Ниже приведен (ограниченный) тип (>=>) и тип оператора (*=>), который мы хотим.

(>=>) :: Monad m => (a -> m a) -> (b -> m  a)  -> a -> m  a
(*=>) :: Monad m => (a -> m a) -> (a -> m [a]) -> a -> m [a]

Определение:

(*=>) :: Monad m => (a -> m a) -> (a -> m [a]) -> a -> m [a]
(*=>) ac uc c = do x  <- ac c
                   xs <- uc x
                   return (x:xs) 

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

execSteps :: Int -> Double -> IO [Double] 
execSteps n = foldr (*=>) (\x -> return []) (steps n) 

Эта функция отличается от оригинальной тем, что в качестве исходного ввода используется Double, а не [Double]. Но это тот тип, который имеет смысл. Вы бы просто передали один обернутый двойник в исходной функции. И он накапливает элементы в «правильном» порядке, как вы просили.