Haskell:迭代状态,如何强制我想要的行为?

Bil*_*kat 4 iteration haskell loops state-monad

这是我在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 []
Run Code Online (Sandbox Code Playgroud)

有了这些定义,

evalState example 1
Run Code Online (Sandbox Code Playgroud)

结果是:

[[],["foo"],["bar","bar"]]
Run Code Online (Sandbox Code Playgroud)

显然,iterate,没有一个!因为该step功能只会在输入列表中添加一些东西,无论状态如何step ["foo"]都无法产生["bar", "bar"]!

让我说,我明白是怎么回事就在这里,还在于-正式-结果正是"理所应当":step是有状态的功能,所以当f(A)上来评价为f的一部分( f(a)),它将被重新计算而不是从第二个列表项中获取,因为状态已经改变.我也意识到,通过将我的累积列表放在状态中,我可以在我的实际应用程序中避免这种情况.

然而,发布这个有两个原因.

首先,关键是iterate经常以一种可能会误导初学者认为它做A的方式,当它实际上做B时.这包括了解你一个Haskell(我发现它非常有用),但也发布在SO(例如这里这里).事实上,iterateLYAHFGG中的口头解释几乎完全是上面的定义A. 因此,它可能会对这个职位是有用的,作为其他的Haskell新手谁得到,因为这是个Bug,并寻找解释(所以通过各种手段做发布更准确,技术,更好的措辞,在澄清的资源下面AB之间差异).

其次,我仍然会感兴趣是否有一个功能实际上会做A!换句话说,在上面的有状态示例中,我怎样才能产生列表(略微滥用符号):[a,b = f(a),f(b),...]?换句话说,给定

example2 = do
           firstResult <- step []
           secondResult <- step firstResult
           return $ [[], firstResult, secondResult]
Run Code Online (Sandbox Code Playgroud)

为此

evalState example2 1
Run Code Online (Sandbox Code Playgroud)

产生所需的结果

[[],["foo"],["bar","foo"]]
Run Code Online (Sandbox Code Playgroud)

我怎么可以重写example2使用iterate

在初学者Haskell列表中,发布了关于记忆版本的相关问题iterate.但是,该查询似乎没有得到答案.

我不完全确定懒惰是我申请中的问题.严格的版本会iterate做我想要的吗?我自己的,天真的,"严格的迭代"如下所示似乎没有任何区别.

iterate' f x = x : rest
               where previous = f x
                     rest = previous `seq` iterate f previous
Run Code Online (Sandbox Code Playgroud)

任何有关所有这些的见解将非常感谢!

Dan*_*her 17

A和B.之间没有区别,参考透明度也是一样的.
问题的核心似乎是你在执行有状态计算的上下文中解释它们.在这种情况下,你期望的
A 的模拟是A':产生结果列表1.将初始计算的结果放入列表中,2.确定前一个结果的下一个计算,执行它并追加结果列表,3.转到2.
B的模拟是
B':产生计算列表(通过迭代(>> =步))并通过一个接一个地执行计算从结果列表中产生计算列表.
对于无状态计算,或者当您将相同的初始状态传递给B'中生成的所有计算时,唯一的区别在于效率,但如果您正在使用sequence,则每个计算都以不同的状态开始,因此您得到的结果与A'不同.打破你的example,我们有

actionList = take 3 $ iterate (>>= step) (return [])
           = [return [], return [] >>= step, return [] >>= step >>= step]
Run Code Online (Sandbox Code Playgroud)

一个动作列表(或monadic值)State Int [String].现在,当你申请时sequence,

example = sequence actionList
Run Code Online (Sandbox Code Playgroud)

你得到一个动作,当执行时,用初始状态运行第一个动作,第二个动作由第一个状态更新,第三个状态由第二个更新.为了获得您期望的行为,它们都必须以相同的初始状态运行.

基本上,类型的值是类型State s v的函数s -> (v, s).iterate创建一个函数列表,并sequence应用这些函数,s为它们提供不同的参数(每个函数都得到s前面生成的参数).

为了获得理想的行为,我们必须引入一个新的组合器.非常好,但只有极少数Monads可用

iterateM :: Monad m => (a -> m a) -> m a -> m [a]
iterateM step start = do
    first <- start
    rest <- iterateM step (step first)
    return (first:rest)
Run Code Online (Sandbox Code Playgroud)

哪个产生

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

但它只能在具有足够懒惰单子(>>=),Control.Monad.State.Lazy是为数不多的,Control.Monad.State.Strict不是.即使有C.M.S.Lazy,你也不能在一个状态之后使用状态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)
Run Code Online (Sandbox Code Playgroud)

所以我们失去了灵活性,但在更多的单子中获得了可用性.