具有上下文传播的无限列表

Question

我想构建一个无限列表，我尝试使用Data.List.iterate，但我需要传播上下文（传播时上下文会发生变化）。

Data.List.iterate属于(a -> a) -> a -> [a] 类型

我需要((a, context)->(a->context)) -> (a, context) -> [a] 之类的东西

到目前为止，我只得到了[(a, context)]，不能做map fst，因为我会得到类似[1, 12, 123, 1234...]的东西，而不是[1, 2, 3, 4....]。

Answer 1

我认为unfoldr正是您想要的：

Prelude> import Data.List(unfoldr)
Prelude Data.List> :t unfoldr
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
Prelude Data.List> let nrs = unfoldr (n -> Just (n,n+1)) 1
Prelude Data.List> take 10 nrs
[1,2,3,4,5,6,7,8,9,10]

它是这样工作的：

你必须给它一个函数，它接受一个状态/上下文（上面的类型b），或者：

• 如果要继续，则返回Just (output,newState)
• 如果要停止，则返回Nothing

因此，如果您总是返回Just ...，则会得到[output]的的无限列表

Answer 2

更新：我错过了问题中的map fst注释，但我不明白为什么它没有产生预期的结果。

---

您可以使用iterate并稍后丢弃上下文：

iter :: ((a, context)->(a, context)) -> (a, context) -> [a]
iter f x = map fst $ iterate f x

懒惰使得CCD_ 17不被进一步应用。只要确保fst . f在context参数中是严格的，这样就不会建立大的thunk。

它也可以内联使用，因为它很短：

> take 15 $ map fst $ iterate ((a,b) -> (b,a+b)) (0,1)
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]