有效的列表通过函数组合附加/前置 [英] efficient list append/prepend through function composition

问题描述

几个月前，我读了一个有效的方法，用O（1）中的其他列表追加和预先列表，并用函数组合来表示它们，一旦求值，就可以在O（n）中生成结果列表。

不幸的是，我不记得这篇文章的来源或者（如果存在）这个技术/方法的名字。你有关于它的参考吗？

解决方案

数据结构称为差异列表（或 DList ）。您可以在Hackage的图书馆 中找到它的默认实现。

正如您所提到的，完整的描述可以从关于这个主题的真实世界Haskell的一章。

Some months ago I read somewhere of an efficient approach for appending and prepending lists to other lists in O(1) by representing them with function compositions that, once evaluated, build in O(n) the resulting list.

Unfortunately I cannot remember the source of this article or (if existing) the name of this technique/approach. Do you have references about it, please?

解决方案

The data structure is called a difference list (or DList for short). You can find a default implementation of it in a library available on Hackage.

As you mentioned, a full description can be gathered from a chapter in Real World Haskell on the subject.

这篇关于有效的列表通过函数组合附加/前置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！