dfe*_*uer 17 haskell applicative finger-tree data-structures
该Applicative实例Data.Sequence通常性能非常好。几乎所有的方法在时间和空间上都是渐进渐近最优的。也就是说，给定完全强制/实现的输入，可以在渐近最优的时间和内存驻留中访问结果的任何部分。还有一个例外：(<*). 我目前只知道两种实现方式：
默认实现
xs <* ys = liftA2 const xs ys
这个实现需要O(|xs| * |ys|)时间和空间来完全实现结果，但只O(log(min(k, |xs|*|ys|-k)))访问k结果的第 th 个元素。
“一元”实现
xs <* ys = xs >>= replicate (length ys)
这只需要O(|xs| * log |ys|)时间和空间，但它不是增量的；访问结果的任意元素需要O(|xs| * log |ys|)时间和空间。
长期以来，我一直认为应该有可能拥有我们的蛋糕并吃掉它，但我从来没有能够很好地处理我脑海中的碎片以达到目标。要做到这一点似乎需要从的实现思路（而不是实际的代码）的组合liftA2和replicate。如何才能做到这一点？
注意：它肯定不会有必要结合像什么rigidify的机制liftA2。类似replicate的部分肯定应该只产生我们rigidify用来从用户提供的树中获得的那种“刚性”结构。
任务完成！我设法找到了一种方法。不幸的是，这对我来说有点太复杂了，无法理解正在发生的一切，而且代码……相当不透明。我会赞成并接受对我所写内容的一个很好的解释，并且也会很高兴地接受关于 GitHub 上的清晰度改进和评论的建议。
非常感谢 Li-Yao Xia 和 Bertram Felgenhauer 帮助清理和记录我的草稿代码。现在它的理解难度大大降低，并将出现在containers. 得到一个答案来结束这个问题仍然会很好。