efficient list append/prepend through function composition
-
19-06-2021 - |
Frage
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?
Lösung
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.
Andere Tipps
You must be thinking of ShowS
and friends from the Prelude. See here.
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow