Algorithms and datastructures are fundamentals in computer programming. Functional data structures have the power to improve the codebase of an application and improve its efficiency. With the advent of functional programming and 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 therefore are very appealing to write robust concurrent programs. But how do we express traditional algorithms in a functional setting? Won’t we end up copying too much? Do we trade performance for versioned data structures? This course attempts to answer these questions by looking at functional implementations of traditional algorithms.
The course begins by showing you the functioning of lists, the workhorse data type for most functional languages. We’ll show you what structural sharing means and how it helps to make immutable data structures efficient and practical.
While writing code, we use ADTs (abstract data types) such as Stacks, Queues, Trees, and Graphs. You’ll see how these ADTs are implemented in a functional setting. We look at implementation techniques such as amortization and lazy evaluation to ensure efficiency. By the end of the course, you’ll be able to write efficient functional data structures and algorithms for your applications.
About the authors
Atul S. Khot grew up in Marathwada, a region of the state of Maharashtra, India. A self-taught programmer, he started writing software in C and C++. A Linux aficionado and a command-line guy at heart, Atul has always been a polyglot programmer. Having extensively programmed in Java and dabbled in multiple languages, these days he is getting increasingly hooked on Scala, Clojure, and Erlang. Atul is a frequent speaker at software conferences, and a past Dr. Dobb's product award judge. In his spare time, he loves to read classic British detective fiction. He is a foodie at heart and a pretty good cook. Atul someday dreams of working as a master chef, serving people with lip-smacking dishes.
He was the author of Scala Functional Programming Patterns published by Packt Publishing in December 2015. The book looks at traditional object-oriented design patterns and shows people how they can use Scala's functional features instead.
Raju Kumar Mishra is a consultant and corporate trainer for big data and programming. After completing his B. Tech from the Indian Institute of Technology (ISM) Dhanbad, he worked for Tata Steel. His deep passion for mathematics, data science, and programming took him to the Institute of Science (IISc). After graduating from IISc in computational science, he worked for Oracle as a performance engineer and software developer.
He is an Oracle-certified associate for Java 7. He is a Hortonworks-certified Apache Hadoop Java developer, and holds a Developer Certification for Apache Spark (O'Reilly School of Technology and Databriks), and Revolution R Enterprise-certified Specialist Certifications. As well as this, he has also passed the Financial Risk Manager (FRM I) exam. His interest in mathematics helped him in clearing the CT3 (Actuarial Science) exam.
In this video, we are going to reverse a list.
In this video, we will be looking at directed graphs, also known as digraphs.
In this video, we will check whether a cycle has been introduced and then print the cycle.
In this video, we will look at the binary operations related to list implementation and then add two binary numbers.
The binary trees' lookup and update operations are fast. So in this video, we will look at all the roots linked up in a list.
In this video, you will first understand about FIFO queues and then learn about functional FIFO queues.
This video deals with the concept of an invariant.
This video deals with the implementation of the priority queues and then we will look at the min-heap data structure first and then the functional version.
A leftist tree is a data structure that we can use to implement the priority queue ADT.
This video deals with development of the functional heaps using leftist tree.
An expression is executed whenever it comes on the way of program execution. This evaluation strategy is known as eager evaluation.
In this video, you will first learn about argument evaluation and then learn about lazy evaluation in Scala and Clojure.
Memoization is the art of computer program optimization to speed up functions.
A stream is generally a lazy and linear sequence collection. Stream elements are evaluated only when needed. In this video, we will look at streams in Scala and Clojure.
In this video, we will look at some mathematical series based algorithms.
In this video, we will take a quick look at how deques are implemented imperatively. Next, we will look at the amortization algorithm technique that underlies this implementation.
The aim of this video is to highlight the difference between strict versus lazy lists.
In this video, we will play a bit with Stream, that is, Scala's lazy lists.
In this video, we will implement dequeues.
In this video, we will get familiarized with some commonly used terms and learn about the almost balanced trees.
In this video, we will look at the core black tree.
In this video, we will verify the transformation and find the complexity of the nodes.
In this video, you will learn what binomial tree is.
A heap-ordered binomial tree is one in which every parent value is less than or equal to its children.
There is a surprising equivalent in the processes of binomial heap insertion and incrementing a binary number.
In this video, you will understand the stable and unstable sorting.
Bubble sort is one of the simplest and oldest algorithms. Each element is compared with the next element.
Selection sort is another simple sorting algorithm. It is a stable sorting algorithm.
Insertion sort is simple to implement and a stable sorting algorithm. During the process of sorting, it creates a sorted subsequence.
Merge sort uses the divide and conquer philosophy
Quick sort is about dividing a problem into approximately similar sub problems, solving each sub problem separately, and combining the results of the sub problems to deliver the final result.
Packt has been committed to developer learning since 2004. A lot has changed in software since then - but Packt has remained responsive to these changes, continuing to look forward at the trends and tools defining the way we work and live. And how to put them to work.
With an extensive library of content - more than 4000 books and video courses -Packt's mission is to help developers stay relevant in a rapidly changing world. From new web frameworks and programming languages, to cutting edge data analytics, and DevOps, Packt takes software professionals in every field to what's important to them now.
From skills that will help you to develop and future proof your career to immediate solutions to every day tech challenges, Packt is a go-to resource to make you a better, smarter developer.
Packt Udemy courses continue this tradition, bringing you comprehensive yet concise video courses straight from the experts.