Haskell：在状态中迭代，如何强制我想要的行为？

Question

这是我在 SO 上的第一篇文章，我对 Haskell 还比较陌生，所以请原谅任何失误或者我的代码不惯用！

考虑以下两个直观描述：a、f(a)、f(f(a))...

A. 包含以下内容的列表：a、f 对 a 的应用、f 对 that 的应用、f 对 that 的应用...

B. 一个列表，在第 i 个位置包含 i 将 f 的应用程序嵌套到 a。

我的问题是，我在尝试使用 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"]]

显然，迭代执行的是B，而不是A！由于 step 函数只会向输入列表添加某些内容，因此 step ["foo"] 不可能产生 [" bar", "bar"]，无论什么状态！

让我说，我确实理解这里发生了什么，而且 - 形式上 - 结果完全是“应该是的”： step 是一个有状态函数，因此，当 f(a) 作为 f(f(a)) 的一部分进行评估时，它将被重新计算，而不是从第二个列表项中获取，因为状态已更改。我还意识到，通过将累积列表放入状态中，我可以在现实应用程序中避免这种情况。

尽管如此，发布此内容有两个原因。

首先，要点是，迭代经常以一种可能会误导初学者的方式进行解释，使其认为它执行A，而实际上它执行B >。这包括 Learn You A Haskell （我发现它非常有用），但也发布在 SO 上（这里和此处）。事实上，LYAHFGG 中对 iterate 的口头解释几乎与上面的定义 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"]]

如何使用iterate重写example2？

在 Haskell 初学者列表中，有一个关于相关问题发布了 iterate 的记忆版本。然而，该询问似乎并未收到答复。

我不完全确定懒惰确实是我的应用程序中的问题。 iterate 的严格版本可以满足我的要求吗？我自己的天真“严格迭代”如下所示，似乎没有任何区别。

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

任何有关这一切的见解将不胜感激！

Answer 1

A. 和 B. 之间没有区别，从引用透明度来看它们是同一件事。
问题的核心似乎是您在执行有状态计算的上下文中解释它们。在这种情况下，您期望的 A 的类似物是
A': 通过 1. 将初始计算的结果放入列表中，2. 根据前一个结果确定下一个计算，执行它并将其结果附加到列表中，3. 转到 2.
B 的类似物是
B'：生成一个计算列表（通过迭代（>>=步骤）），并通过逐个执行计算来生成结果列表。
对于无状态计算，或者当您将相同的初始状态传递给 B' 中生成的所有计算时，唯一的区别在于效率，但如果您使用 sequence，则每个计算都会以不同的状态开始，所以你会从 A' 得到不同的结果。
分解您的示例，我们

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代码> 由前面生成）。

为了获得所需的行为，我们必须引入一个新的组合器。非常好，但只能在很少的 Monad 中使用，

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"]]

But it 仅在具有足够惰性的 monad 中工作 (>>=), Control.Monad.State.Lazy 是少数之一，Control.Monad.State.Strict 是不是。即使使用CMSLazy，您也无法使用iterateM之后的状态，您必须put一个新状态才能继续计算。为了获得可与其他 monad 一起使用的东西，我们可以添加一个 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)

因此我们失去了灵活性，但在更多 monad 中获得了可用性。

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"]]

不需要单子。我有点摸不着头脑，因为你没有具体说明你实际上想要做什么，但无论我的步骤是否正确，要点是unfoldr 也可用于简单状态线程。

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