4

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

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

A. 一个列表,包含:a、f 对 a 的应用、f 对那个的应用、f 对那个的应用……

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

我的问题是我试图使用iterateHaskell 中的函数来做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"]]

显然,iterateB,而不是A!因为该step函数只会在输入列表中添加一些内容,所以无论状态如何,step ["foo"]都不可能导致!["bar", "bar"]

让我说我确实理解这里发生了什么,而且 - 正式 - 结果正是“应该是”:step是一个有状态的函数,所以当 f(a) 作为 f( f(a)),它将被重新计算,而不是从第二个列表项中取出,因为状态已经改变。我也意识到我可以通过将我的累积列表放入状态中来避免在我的实际应用程序中发生这种情况。

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

首先,重点iterate是经常以一种可能误导初学者认为它是A的方式来解释它,而实际上它是B。这包括Learn You A Haskell(否则我发现它非常有用),但也可以在 SO 上发布(例如, herehere)。事实上,iterateLYAHFGG 中的口头解释几乎就是上面的定义A。因此,在此发布一个帖子可能是有用的,作为其他 Haskell 新手的资源,他们因此而遇到错误并正在寻找解释(所以一定要发布更准确、技术性、措辞更好的澄清A和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

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

4

2 回答 2

17

A. 和 B. 之间没有区别,它们是参照透明性的同一件事。
问题的核心似乎是您在执行有状态计算的上下文中解释它们。在这种情况下,您期望的 A 的类似物是
A':通过 1. 将初始计算的结果放入列表中,2. 确定下一个计算,执行它并追加它的结果到列表中, 3. 转到 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

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

基本上, type 的值是 typeState 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不是。即使使用,您也不能使用 之后的状态,您必须先进入新状态,然后才能继续计算。为了得到其他 monad 可用的东西,我们可以添加一个 count 参数,C.M.S.LazyiterateMput

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)

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

于 2011-10-28T11:04:12.683 回答
3

这可能无法回答您提出的问题,但您正在做的事情听起来很像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]
于 2011-10-29T06:03:06.713 回答