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(例如这里和这里).事实上,iterate
LYAHFGG中的口头解释几乎完全是上面的定义A. 因此,它可能会对这个职位是有用的,作为其他的Haskell新手谁得到,因为这是个Bug,并寻找解释(所以通过各种手段做发布更准确,技术,更好的措辞,在澄清的资源下面A和B之间的差异).
其次,我仍然会感兴趣是否有一个功能实际上会做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)
所以我们失去了灵活性,但在更多的单子中获得了可用性.