Haskell: итерация в состоянии, как заставить поведение, которое я хочу?

Question

Это моя первая публикация на SO, и я относительно новичок в Haskell, поэтому прошу прощения за любые ошибки или если мой код не идиоматичен!

Рассмотрим следующие два интуитивных описания: a, f(a), f (f (a)) ...

A. список, содержащий: a, применение f к a, применение f к , что, применение f к , что ...

B. список, содержащий в i-й позиции вложенные приложения f к a.

Моя проблема в том, что я сгорел, пытаясь использовать функцию iterate в Haskell для выполнения A .Мое настоящее приложение - симуляция, но следующий надуманный пример выдвигает на первый план проблему.

import Control.Monad.State

example :: State Int [[String]]

step :: [String] -> State Int [String]
step l = do
         currentState <- get
         let result = if (currentState == 1)
                          then "foo":l
                          else "bar":l
         put (currentState + 1)
         return result

example = do
          sequence $ take 3 . iterate (>>= step) $ return []

С этими определениями

evalState example 1

приводит к:

[[],["foo"],["bar","bar"]]

Очевидно, что iterate делает B , а не A !Поскольку функция step только когда-либо добавляет что-то в список ввода, step ["foo"] не может привести к ["bar", "bar"], независимо от состояния!

Позвольте мне сказать, что я do понять, что здесь происходит, а также то, что - формально - результат в точности "как и должно быть": step - это функция с состоянием, поэтому, когда f (a) подходит для оценки какчасть f (f (a)), она будет пересчитана, а не взята из второго элемента списка, потому что состояние изменилось.Я также понимаю, что мог бы избежать этого в своем реальном приложении, поместив свой накопительный список в состояние.

Тем не менее, есть две причины для публикации этого.

Во-первых, дело в том, чтоiterate часто объясняется таким образом, что потенциально может ввести новичка в заблуждение, полагая, что он делает A , тогда как на самом деле это B .Это включает в себя Learn You A Haskell (что я иначе счел невероятно полезным), а также публикацию на SO ( здесь и здесь , например).Фактически, словесное объяснение iterate в LYAHFGG - это почти точно определение A выше.Поэтому может быть полезно иметь пост на эту тему, который будет служить ресурсом для других новичков на Haskell, которые получают ошибку из-за этого и ищут объяснения (так что непременно публикуйте более точные, технические, лучше сформулированные пояснения поразница между A и B ниже).

Во-вторых, мне все равно будет интересно, есть ли функция, которая на самом деле выполняет A !Другими словами, как я могу в приведенном выше примере с состоянием создать список (с небольшим злоупотреблением обозначениями): [a, b = f (a), f (b), ...]?Другими словами, учитывая

example2 = do
           firstResult <- step []
           secondResult <- step firstResult
           return $ [[], firstResult, secondResult]

, для которого

evalState example2 1

дает желаемый результат

[[],["foo"],["bar","foo"]]

Как я могу переписать example2, используя iterate?

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

Я не совсем уверен, что лень действительно является проблемой в моем приложении.Будет ли строгая версия iterate делать то, что я хочу?Моя собственная, наивная, «строгая итерация», как показано ниже, не имеет никакого значения.

iterate' f x = x : rest
               where previous = f x
                     rest = previous `seq` iterate f previous

Любое понимание всего этого будет высоко ценится!

Answer 1

Нет разницы между А. и Б., они - это одно и то же по ссылочной прозрачности.
Суть проблемы заключается в том, что вы интерпретируете их в контекстевыполнение вычислений с учетом состояния.В этом контексте ожидаемым аналогом A является
A ': создайте список результатов, 1. поместив результат начального вычисления в список, 2. определите следующее вычисление из предыдущего результата и выполнитеи добавьте свой результат в список, 3. перейти к 2.
Аналогом B является
B ': создать список вычислений (путем итерации (>> = шаг)) и из этого списка результатов:выполнение вычислений одно за другим.
Для вычислений без сохранения состояния или когда вы передаете одно и то же начальное состояние всем вычислениям, произведенным в B ', единственное различие заключается в эффективности, но если вы используете sequence, каждое вычислениеначинается с другого состояния, поэтому вы получаете разные результаты от A '.Разбивая ваши example, мы имеем

actionList = take 3 $ iterate (>>= step) (return [])
           = [return [], return [] >>= step, return [] >>= step >>= step]

список действий (или монадических значений) в State Int [String].Теперь, когда вы применяете sequence к этому,

example = sequence actionList

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

По сути, значение типа State s v является функцией типа s -> (v, s).iterate создает список функций, а sequence применяет эти функции, предоставляя им различные s аргументы (каждый получает s, созданный предыдущим).

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

iterateM :: Monad m => (a -> m a) -> m a -> m [a]
iterateM step start = do
    first <- start
    rest <- iterateM step (step first)
    return (first:rest)

, который производит

Prelude Control.Monad Control.Monad.State> evalState (fmap (take 4) (iterateM step (return []))) 1
[[],["foo"],["bar","foo"],["bar","bar","foo"]]

Но он работает только в монадах с достаточно ленивым (>>=), Control.Monad.State.Lazy является одним изнемногие, Control.Monad.State.Strict - это , а не .И даже с C.M.S.Lazy вы не можете использовать состояние после iterateM, вам необходимо put новое состояние, прежде чем вы сможете продолжить вычисление.Чтобы получить что-то полезное с другими монадами, мы могли бы добавить параметр count

iterCountM :: (Monad m) => Int -> (a -> m a) -> m a -> m [a]
iterCountM 0 _ _ = return []
iterCountM k step start = do
    first <- start
    rest <- iterCountM (k-1) step (step fisrt)
    return (first:rest)

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

Answer 2

Это может не отвечать на заданный вами вопрос, но то, что вы делаете, звучит очень похоже на unfoldr.

step (seed, l) = Just (l', (seed', l'))
  where seed' = succ seed
        l' = (if seed == 1 then "foo" else "bar"):l

---

ghci> take 3 $ unfoldr step (1, [])
[["foo"], ["bar", "foo"], ["bar", "bar", "foo"]]

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

unfoldr :: (seed -> Maybe (val, seed)) -> seed -> [val]