Haskell中applyN与composeN函数是否具备功能等价性？

结论先行：对于非负整数n、任意纯函数f :: a -> a以及值x :: a，两个实现的返回结果完全一致，但在负数n的边缘场景、懒加载行为和性能表现上存在差异。

1. 结果等价性（非负n场景） #

我们可以从语义上证明二者的结果一致：

• applyN n f x 的逻辑是通过iterate f x生成无限列表[x, f x, f (f x), ..., f^n x, ...]，再通过!! n取出第n个元素，本质是将f重复应用n次到x上，即f^n x。
• composeN n f x 的逻辑是先通过replicate n f生成包含n个f的列表，再用foldr (.) id将这些函数依次组合成f . f . ... . f（共n次组合），最后作用在x上，结果同样是f^n x。

对于n=0的边界情况：

• applyN 0 f x 直接取iterate f x的第0个元素，即x；
• composeN 0 f x 对空列表执行foldr (.) id得到id，作用在x上也返回x。

用数学归纳法可推广到所有非负整数n，二者的计算结果完全相同。

2. 边缘场景差异：负数n #

当n为负整数时，两个实现的行为完全不同：

• applyN n f x 会触发Prelude.(!!): negative index异常，因为(!!)不支持负数索引；
• composeN n f x 中replicate n f会返回空列表（Haskell中replicate对负数n返回空），最终等价于id x，返回x本身。

3. 懒加载与性能差异 #

虽然结果一致，但二者的计算过程和内存表现有区别：

• applyN：依赖iterate生成惰性列表，(!! n)会迫使生成前n+1个元素。如果n很大，会在内存中保留整个中间列表（直到被GC回收），可能占用更多内存；但好处是如果后续需要复用前面的元素（比如再次调用!! k，k<n），可以直接取用已生成的结果。
• composeN：通过函数组合生成一个嵌套的闭包\x -> f(f(...(f x)...))，应用到x时会直接执行n次f调用，不会生成中间列表，内存占用更高效；但如果需要复用不同次数的应用结果，无法直接复用，需要重新组合函数。

对于带有副作用的调试函数（比如f = trace "called" (+1)），二者的副作用触发次数完全一致（都是n次），因为每次f的应用都会触发一次trace。

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