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

Question

这是我在SO上的第一个帖子，我对Haskell比较陌生，所以如果我的代码不习惯，请原谅我的任何错误!

考虑以下两个直观的描述:a, f(a)， f(f(a))…

a . a, f对a的应用，f对的应用，， f对的应用，…

b . 在第I个位置，包含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 , !因为step函数只会向输入列表中添加，所以step ["foo"]不可能产生["bar", "bar"]，无论状态如何!

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

尽管如此，我还是有两个理由发表这篇文章。

首先，重点是iterate经常以一种可能误导初学者认为它执行 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。goto 2。
B的类似物是
B':生成一个计算列表(通过迭代(>>= step))，并通过一个接一个地执行计算，从该列表生成一个结果列表。
对于无状态计算，或者当您将相同的初始状态传递给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)。

为了得到期望的行为，我们必须引入一个新的组合子。非常好，但只能在极少数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"]]

但是它只在具有足够延迟的(>>=)的单子中工作，Control.Monad.State.Lazy是少数几个之一，Control.Monad.State.Strict是而不是。即使使用C.M.S.Lazy，您也不能使用iterateM之后的状态，您必须在put之前创建一个新状态才能继续计算。为了使其他单子可用，我们可以添加一个计数参数

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]