Book Image

Learning F# Functional Data Structures and Algorithms

By : Adnan Masood
Book Image

Learning F# Functional Data Structures and Algorithms

By: Adnan Masood

Overview of this book

Table of Contents (21 chapters)
Learning F# Functional Data Structures and Algorithms
Credits
Foreword
Foreword
Foreword
About the Author
Acknowledgments
About the Reviewers
www.PacktPub.com
Preface
Index

Vectors


Lists are an effective data structure when the processing is focused mainly on the head element, which takes a constant time to access. For the elements further within the list, the access time is linearly proportional to the depth of the list, that is, their position within the list. This random access issue on the list is addressed by vectors in various functional (or multi-paradigm) programming languages such as Scala. Scala is to JVM what F# is to .NET. A vector is built as a collection type based on bit-mapped vector tries, providing a solution to the inadequacy of random access on lists.

Note

A discussion on bit vector optimization and tries are beyond the scope of this book. However, you can find an excellent talk on Persistent Data Structures and Managed References by Rich Hickey, the author of Clojure at www.infoq.com/presentations/Value-Identity-State-Rich-Hickey.

The conventional implementation of vectors can rapidly access an indexed array element. However, a bitmapped vector...