Learning Functional Data Structures and Algorithms

Learn functional data structures and algorithms for your applications and bring their benefits to your work now

About This Book

• Moving from object-oriented programming to functional programming? This book will help you get started with functional programming.
• Easy-to-understand explanations of practical topics will help you get started with functional data structures.
• Illustrative diagrams to explain the algorithms in detail.
• Get hands-on practice of Scala to get the most out of functional programming.

Who This Book Is For

This book is for those who have some experience in functional programming languages. The data structures in this book are primarily written in Scala, however implementing the algorithms in other functional languages should be straight forward.

What You Will Learn

• Learn to think in the functional paradigm
• Understand common data structures and the associated algorithms, as well as the context in which they are commonly used
• Take a look at the runtime and space complexities with the O notation
• See how ADTs are implemented in a functional setting
• Explore the basic theme of immutability and persistent data structures
• Find out how the internal algorithms are redesigned to exploit structural sharing, so that the persistent data structures perform well, avoiding needless copying.
• Get to know functional features like lazy evaluation and recursion used to implement efficient algorithms
• Gain Scala best practices and idioms

In Detail

Functional data structures have the power to improve the codebase of an application and improve efficiency. With the advent of functional programming and with powerful functional languages such as Scala, Clojure and Elixir becoming part of important enterprise applications, functional data structures have gained an important place in the developer toolkit. Immutability is a cornerstone of functional programming. Immutable and persistent data structures are thread safe by definition and hence very appealing for writing robust concurrent programs.

How do we express traditional algorithms in functional setting? Won t we end up copying too much? Do we trade performance for versioned data structures?

This book attempts to answer these questions by looking at functional implementations of traditional algorithms.

It begins with a refresher and consolidation of what functional programming is all about. Next, you ll get to know about Lists, the work horse data type for most functional languages. We show what structural sharing means and how it helps to make immutable data structures efficient and practical.

Scala is the primary implementation languages for most of the examples. At times, we also present Clojure snippets to illustrate the underlying fundamental theme. While writing code, we use ADTs (abstract data types). Stacks, Queues, Trees and Graphs are all familiar ADTs. You will see how these ADTs are implemented in a functional setting. We look at implementation techniques like amortization and lazy evaluation to ensure efficiency.

By the end of the book, you will be able to write efficient functional data structures and algorithms for your applications.

Style and approach

Step-by-step topics will help you get started with functional programming. Learn by doing with hands-on code snippets that give you practical experience of the subject.

學習功能性資料結構和演算法，並將其優勢應用於您的應用程式，立即提升您的工作效能。

關於本書
- 從物件導向程式設計轉向功能性程式設計？本書將幫助您入門功能性程式設計。
- 簡單易懂的實用主題解說，幫助您入門功能性資料結構。
- 以圖解方式詳細解說演算法。
- 透過實作 Scala 來實踐功能性程式設計。

本書適合對功能性程式語言有一定經驗的讀者。本書中的資料結構主要使用 Scala 編寫，但在其他功能性程式語言中實作這些演算法也應該很直觀。

您將學到什麼
- 學習以功能性範式思考
- 了解常見的資料結構、相關演算法以及常見應用情境
- 了解 O 記法中的執行時間和空間複雜度
- 瞭解在功能性環境中如何實作抽象資料類型（ADTs）
- 探索不可變性和持久化資料結構的基本主題
- 瞭解如何重新設計內部演算法以利用結構共享，使持久化資料結構表現良好，避免不必要的複製
- 瞭解實現高效演算法所使用的功能性特性，如延遲評估和遞迴
- 掌握 Scala 的最佳實踐和慣用法

詳細內容
功能性資料結構能夠改善應用程式的程式碼庫並提高效能。隨著功能性程式設計的興起，以及強大的功能性程式語言（如 Scala、Clojure 和 Elixir）成為重要企業應用程式的一部分，功能性資料結構在開發者工具包中佔據重要地位。不可變性是功能性程式設計的基石。不可變和持久化資料結構在定義上是線程安全的，因此非常適合編寫堅固的並行程式。

我們如何在功能性環境中表達傳統演算法？我們會不會因此複製太多資料？我們是否為版本化資料結構而犧牲效能？

本書試圖通過探索傳統演算法的功能性實作來回答這些問題。

本書首先回顧並鞏固了功能性程式設計的基礎知識。接下來，您將了解到列表（List），這是大多數功能性程式語言中最常用的資料類型。我們將展示結構共享的意義以及它如何幫助實現不可變資料結構的效能和實用性。

Scala 是大多數範例的主要實作語言。有時，我們也會使用 Clojure 片段來說明基礎主題。在編寫程式碼時，我們使用抽象資料類型（ADTs）。堆疊（Stacks）、佇列（Queues）、樹（Trees）和圖（Graphs）都是熟悉的 ADTs。您將看到這些 ADTs 如何在功能性環境中實作。我們將探討攤銷和延遲評估等實作技巧，以確保效能。

通過閱讀本書，您將能夠為應用程式編寫高效的功能性資料結構和演算法。

風格和方法
逐步的主題將幫助您入門功能性程式設計。通過實際經驗的程式碼片段進行實作，讓您獲得實際的學習體驗。