Случайный список, где каждый элемент отличается максимум на 1 от предыдущего элемента - PullRequest
Новая
       45

Случайный список, где каждый элемент отличается максимум на 1 от предыдущего элемента

5 голосов
/ 16 марта 2019

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

import Data.List
import System.Random

step :: Int -> IO Int
step n = (+n) <$> randomRIO (-1, 1)

steps :: Int -> Int -> IO [Int]
steps n = sequence . take n . iterate' (>>= step) . return

(я также пробовал с нестрогой функцией iterate, которая дала мне тот же результат).

Функция step принимаетinteger и, случайным образом, добавляет -1, 0 или 1 к нему.Функция steps принимает количество итераций и начальное целое число и применяет step правильное количество раз.

Проблема в том, что steps дает мне такие вещи, как [0,1,-1,0,1,1,1,3], чтонеправильно.Похоже, каждый элемент создается каждый раз с нуля, тогда как я хочу, чтобы каждый элемент зависел от предыдущего.По этой причине я решил использовать iterate' вместо iterate, что говорит о том, что перед продолжением каждая итерация сводится к WHNF, но даже все равно это не работает.

Затем я понял, что проблема можетвозникают из-за того, что он на самом деле генерирует список, который выглядит примерно так: 

[ n,
  n >>= step,
  n >>= step >>= step
  ... ]

И тогда кажется ясным, почему это происходит.Итак, мой вопрос, могу ли я предотвратить это?Могу ли я заставить Haskell оценивать каждый элемент по мере его продвижения?Существует ли строгая версия оператора >>=?

(Правка: я подумал, что было бы полезно привести пример списка, который я ищу, а не просто описать его. [0, 1, 2, 1, 2, 1, 0, -1], например)

1 Ответ

8 голосов
/ 16 марта 2019

Вам не нужна строгая версия >>=.Вам нужен монадический вариант для iterate.В конце концов, вы уже определили свою проблему, вы строите бесконечное число вычислений : 

[ return x , return x >>= step, return x >>= step >>= step, ... ]

Вам понадобится монадический вариант iterate: 

-- This function does not work, but shows the principle we would
-- want from such a function.
iterateM :: Monad m => (a -> m a) -> a -> m [a]
iterateM f x = do
     y  <- f x
     ys <- iterateM f y -- << this never terminates
     return (y:ys)

Тем не менее, этот вариант не существует *, так как он не прекращается, по тем же причинам, по которым forM [1..] return не прекращается.Однако мы можем это исправить, если изменить алгоритм на , сначала сгенерировать различия с replicateM, а затем sum с этими различиями с scanl: 

import Control.Monad (replicateM)
import System.Random (randomRIO)

step :: IO Int
step = randomRIO (-1, 1)

steps :: Int -> Int -> IO [Int]
steps n x = scanl (+) x <$> replicateM n step

В этом случае у нас есть ограниченное число step s в IO и мы используем обычный scanl для создания желаемого списка.

* В потоковых библиотеках есть несколько вариантовгде потребитель может решить, могут ли вычисления выполняться.iterateM может быть реализовано там, например, в ConduitM.

...