Haskell如何构建指定长度、由初始值迭代生成元素的列表

为什么replicate无法直接实现需求 #

replicate的函数签名为replicate :: Int -> a -> [a]，作用是将第二个输入的固定值重复指定次数生成列表，无法实现「逐次对前一个元素应用函数生成新元素」的逻辑，因此你最初的思路确实不可行，使用iterate是更合理的选择。

基于iterate的最优实现 #

iterate的函数签名为iterate :: (a -> a) -> a -> [a]，会生成一个无限长的迭代序列：从传入的初始值开始，每一位元素都是前一位元素应用指定函数得到的结果，刚好匹配你需要的[x, f x, f(fx), ...]生成规则，只需要截取前len位即可得到目标列表。

实现代码如下：

buildList::Int -> (b -> b) -> b -> [b]
buildList len func initial = take len $ iterate func initial

示例验证 #

调用buildList 5 (*2) 1，输出结果为[1,2,4,8,16]，符合需求。

（不推荐）基于replicate的实现思路 #

如果一定要用replicate完成需求，可以用索引映射的方式实现，代码如下：

buildList len func initial = map (\i -> foldr (.) id (replicate i func) initial) [0..len-1]

该方案存在大量重复计算，时间复杂度为O(n²)，效率远低于基于iterate的实现，仅做思路参考不建议实际使用。

内容的提问来源于stack exchange，提问作者user1612508