O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

41

Functional Data Structures*

Chris Okasaki

United States Military Academy

41.1Introduction

Data Structures in Functional LanguagesFunctional Data Structures in Mainstream Languages

41.2Stacks: A Simple Example

41.3Binary Search Trees: Path Copying

41.4Skew Heaps: Amortization and Lazy Evaluation

Analysis of Lazy Skew Heaps

41.5Difficulties

41.6Further Reading

Acknowledgments

References

41.1Introduction

A functional data structure is a data structure that is suitable for implementation in a functional programming language, or for coding in an ordinary language like C or Java using a functional style. Functional data structures are closely related to persistent data structures and immutable data structures—in fact, the three terms are often ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required