Purely functional data structure: Difference between revisions

Revision as of 20:02, 30 September 2017

Revision as of 20:06, 30 September 2017

Line 29:

===Laziness and memoization===

[[Lazy evaluation]] is particularly interesting in a purely functional language because the order of the evaluation never changes the result of a function. Therefore, lazy evaluation naturally becomes an important part of the construction of purely functional data structures. It allows computationcomputations to be done only when its result is actually required. Therefore, the code of a purely functional data structure can, without loss of efficiency, consider similar data whichthat will effectively be used and data whichthat will be ignored. The only computation required is for the first kind of data that will actually be performed.

One of the key tools in building efficient, purely functional data structures is [[memoization]]. When a computation is done, it is saved and does not have to be performed a second time. This is particularly important in lazy implementations; additional evaluations may require the same result, but it is impossible to know which evaluation will require it first. There are actually many books that pertain to purely functional data structures that can give you a more in depth sight of laziness and memoization.

===Amortized analysis and scheduling===