Lesson plan
Difference list
In computer science, the term difference list refers to a data structure representing a list with an efficient O(1) concatenation operation and conversion to a linked list in time proportional to its length. Difference lists can be implemented using first-class functions or using unification. Whether a difference list is more efficient than other list representations depends on usage patterns. If an algorithm builds a list by concatenating smaller lists, which are themselves built by concatenating still smaller lists, then the usage of difference lists can improve performance by effectively "flattening" the list building computations.
Article summary
In computer science, the term difference list refers to a data structure representing a list with an efficient O(1) concatenation operation and conversion to a linked list in time proportional to its length. Difference lists can be implemented using first-class functions or using unification. Whether a difference list is more efficient than other list representations depends on usage patterns. If an algorithm builds a list by concatenating smaller lists, which are themselves built by concatenating still smaller lists, then the usage of difference lists can improve performance by effectively "flattening" the list building computations.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.