F# Functional Data Structures

This course describes the important data structures - especially collections - available in F#, together with the functions which F# provides for working with them.
Course info
Rating
(194)
Level
Intermediate
Updated
Aug 14, 2014
Duration
3h 44m
Table of contents
Introduction
Arrays
Sequences
Lists
Lists, Pattern Matching, and Recursion
Dictionaries
Sets and Maps
Trees
Choosing a Data Structure
Description
Course info
Rating
(194)
Level
Intermediate
Updated
Aug 14, 2014
Duration
3h 44m
Description

F# and .NET provide you with a wealth of data structures and collections for storing and manipulating data. This course identifies these structures and the functions which F# provides to work with them, including arrays, lists, and sequences. By the end of the course you'll know how to write idiomatic, maintainable programs which solve complex problems with simple code.

About the author
About the author

Kit has been a software developer since the 1980s, working in industries from automotive engineering to energy trading. He's known for his huge enthusiasm for F#, which he will share with anyone who will listen.

More from the author
F# Jumpstart
Beginner
1h 25m
Jul 3, 2015
Section Introduction Transcripts
Section Introduction Transcripts

Introduction
Hello. My name is Kit Eason. Welcome to the F# Functional Data Structures course, Module 1, Introduction. In this introductory module I'll be talking about what a functional data structure is and why functional data structures are important to F# programmers. I'll also talk about the prerequisites for the course in terms of your understanding of F# syntax, but don't worry, this introduction also includes brief reviews of all the keywords and concepts you'll need. So if you're relatively new to F# or perhaps a bit rusty, you should still be able to keep up fine. We'll start by asking why functional data structures matter. They matter because this is where you get the payoff for learning F#. If you're not using data structures correctly and idiomatically, then F# is essentially just another syntax. Once you do start using them correctly you'll realize why F# is such a revolutionary language. You'll be able to use this combination, F# language features together with functional data structures, to do extraordinary things with small amounts of code. Your bug count will plummet and your productivity, measured in terms of correct functionality delivered over time, will soar. By the way, I'll be using the idiomatic a lot in this course. By idiomatic I mean code which is written in a style which makes best use of F#'s features, and of course the functional data structures. Now, if you're wondering how a very relatively straightforward data structures can make such a difference, you're right, to get the benefit we need to know about both the structures and the associated operations which F# provides. In fact, this course will spend as much, if not more, time on what F# lets you do to and with the structures as on the structures themselves.

Arrays
Welcome to Pluralsight. I'm Kit Eason and you are watching the F# Functional Data Structure course, Module 2, Arrays. Although arrays are a staple of programming in most languages, F# provides some very special features for working with arrays. This module will give you a thorough grounding in F#'s approach to array processing. You'll also learn some fundamental techniques, which will serve you well across many other data structures. If you've coded in virtually any language then arrays will be very familiar. They're a standard. NET type, their length is fixed on creation, and all elements of the array are each of the same type, although that type itself can be arbitrarily complex. So what's different in F# land? One thing to note, it's important to know this about any type when you're using it from F#, is the mutability of an array. The array as a whole is immutable by default. You can't assign to the structure as a whole once you've created, but the individual elements are always mutable. You can replace any one of them with some other value, of the correct type of course, at any time. We'll show how in a moment.

Sequences
Welcome to Pluralsight. I'm Kit Eason and you are watching the F# Functional Data Structures course, Module 3, Sequences. Now we understand how F# deals with arrays, it's time to look at a structure which is more F# specific, a sequence. If an array is a series of actual values, a sequence is a list of potential values, each of which is computed on demand. Like an array, a sequence has elements which are all of the same type. Unlike an array, these elements are immutable, you can't assign to them. If you're familiar with. NET and C#, you'll recognize sequences as being IEnumerables. What F# brings to the party is some very rich syntax and library functionality for creating and processing sequences.

Lists
Welcome to Pluralsight. I'm Kit Eason and you're watching the F# Functional Data Structure course, Module 4, Lists. We're going to look at yet another collection, the F# list. Luckily F# lists have a lot in common with arrays and sequences, so we can get the basics over pretty quickly. Then we can go on and look at the cool things you can do with lists, such as recursive processing and _____. These are what make lists the structure of choice for many idiomatic F# algorithms. A list is a list of elements. The elements are computed on creation, unlike a sequence, they must all be of the same type, and the elements are immutable. Behind the scenes F# lists are implemented as linked lists, in other words the first element has a secret pointer to the second element, the second to the third, and so on. One thing to get clear from the outset is that an F# list is not the same thing as a C# list. The naming clash comes from F#'s ML ancestry. Here's how the naming pans out. A C# list is from System. Collections. Generic and is mutable, that is it has methods to add and remove items from itself. When used from F#, this kind of list is exposed as a resize array. An F# sharp list is what we're talking about today. It comes from the Microsoft. FSharp. Collections namespace and is immutable.

Lists, Pattern Matching, and Recursion
Welcome to Pluralsight. I'm Kit Eason and you're watching the F# Functional Data Structure course, Module 5, Lists, Pattern Matching, and Recursive Processing. In this module we're going to extend our understanding of lists by applying pattern matching and recursive processing. If you grasp these topics you'll be a truly fluent F# developer. We need to make sure we understand pattern matching in general F# code. Once we're secure on that we'll apply it to lists. Pattern matching has nothing to do with regular expressions or image processing, instead it's a language feature which allows you to branch logic and assign values according to the shape, as well as the value of data items. Pattern matching's most obvious application is F#'s match construct, so let's look at that.

Dictionaries
Welcome to Pluralsight. I'm Kit Eason and you're watching the F# Functional Data Structures course, Module 6, Dictionaries. In this module we're going to learn how to make best use of. NET dictionaries from F#. It's important that you have a good grasp of the dictionary class and of the best ways of making use of it from F#. This will help you write high performance applications, which scale well with large data sets. We'll also look at ConcurrentDictionary, which we'll need to use when multiple threads are updating and reading a dictionary concurrently.

Sets and Maps
Welcome to Pluralsight. I'm Kit Eason and you're watching the F# Functional Data Structures course, Module 7, Sets and Maps. In this module we'll introduce F# sets and maps. These structures let you construct correct and readable algorithms for building and using unique sets and maps, a map being effectively an immutable dictionary. They're important tools in the toolbox of the skilled F# developer because they let you code succinctly in an immutable style. A set in F# terms is a collection of instances of any type where the set can only contain one copy of any given value. And actually when I say a set can contain any type, the type will at least need to implement comparison. Since this is an immutable type, adding an item doesn't really mean changing the set, it means generating a new set containing the original set's items plus the new item. At first site this might seem wasteful, but as with the list type most of the storage nodes from the original set are simply reused. It's not an error to add a duplicate value, but the additional value will simply be ignored.

Trees
Welcome to Pluralsight. I'm Kit Eason and you're watching the F# Functional Data Structures course, Module 8, Trees. In this module we'll introduce trees and the various ways you can represent and work with trees in F#. It's an important topic because trees are everywhere. Topics as diverse as human ancestry and the structure of file storage on your disk drive can be succinctly represented as tree structures. Although conceptually simple, they can be tricky to represent effectively. Fortunately it's an area in F# excels. It's probably worth pausing before we plunge into code to establish some common terminology for the various parts of a tree structure. A tree consists of nodes, the top-most node is the root node, it's the only one without any parents. A parent node is a node which has at least one child. A node with no children is a leaf. Perhaps a little confusingly the connection between one node and another is called an edge, although actually we won't have occasion to use that term in this module.

Choosing a Data Structure
Welcome to Pluralsight. I'm Kit Eason and you're watching the F# Functional Data Structures course, Module 9, Choosing a Data Structure. In this module we'll look at the factors you need to take into account when choosing the data structures to use in your programs. Selecting the right data structure from the outset can save you a lot of heartache through the lifecycle of the software you're writing. It's also a good opportunity to review some of the information we covered in earlier modules. So, what are the big topics we need to consider when selecting a data structure? I think you need to start with the major considerations any business or organization will have in mind, consciously or otherwise, when approaching a software project. These are productivity, can the developer or developers produce a working system in a reasonable period of time? Reliability including correctness. Will the system work correctly and continue to work correctly every time? Maintainability. As features are added or problems discovered you or someone else is going to have to understand and change the code. Are other people or future you going to be able to understand what is going on and make the changes with confidence? Performance including scalability. Will the system process data fast enough and remain performing when faced with realistic amounts of data? We're going to examine each of these big picture considerations and show how the data structure choices you make can influence success in each area.