Preface

F# is a multiparadigm programming language that encompasses object-oriented, imperative, and functional programming language properties. The functional paradigm can be defined as programming with pure functions, programming by function composition, and a combination of both. For over a quarter of a century, functional programming languages such as Lisp, Haskell, and standard ML existed in academia, but industry adaption has been quite slow. With the introduction of F#, an open source functional programming language, this trend is witnessing a significant change. F# runs on the .NET runtime and supports libraries from other IL-based programming languages.

Due to the seemingly overarching title of this manuscript, a few disclaimers are in order. This book is an introduction to F#, functional data structures, and algorithms. These topics are fairly large in their inpidual capacity. A large body of growing literature exists in each of these areas itself. Therefore, it won't be a reasonable expectation to provide a comprehensive picture of data structures and algorithms in the limited amount of space available in this book. Instead, this book is intended as a cursory introduction to the use and development of data structures and algorithms using F#. The goal is to provide a broader overview and resources to the reader to get started with functional programming using F#.

This book is written with a few assumptions, keeping the reader in mind. We assume that the reader has basic knowledge of an imperative programming language and object-oriented concepts. Readers are highly encouraged to try out examples, use the resources listed in Chapter 10, Where to Go Next?, and review specialized texts for a more comprehensive treatment of algorithms and data structures.

Starting with the basic concepts of F#, this book will help you to solve complex computing problems with simple, maintainable, and robust code. Using easy-to-understand examples, you will learn how to design data structures and algorithms in F# and apply these concepts in real-life projects, as well as gain insights into how to reuse libraries available in community projects. You will also learn how to set up Visual Studio .NET and F# compiler to work together, implement the Fibonacci sequence and Tower of Hanoi using recursion, and apply lazy evaluation for quick sorts. The book will then cover built-in data structures and take you through enumerations and sequences. You will gain knowledge about stacks, graph-related algorithms, and implementations of binary trees. Next, you will understand the custom functional implementation of a queue and look at the already available collection and concurrent collection structures. You will also review sets and maps and explore the implementation of a vector.

In the final leg of this book, you will find resources and references that will give you a great overview of how to build an application in F# and do great things. We have tried our best to provide attribution to all the resources used in this book. However, if anything has been missed, let us know. To build upon the fundamentals you would learn in this book, we have created a code repository to solve project Euler algorithmic problems. Project Euler is a series of challenging mathematical and computer programming problems that require working with algorithms and data structures. You will see our solutions on the GitHub repo at https://github.com/adnanmasood/Euler.Polyglot.

In the cover, the choice of lush landscape and central figure reminiscent of general Sherman trail is an attempt to portray the variety of programming paradigms and the potential strength of functional concepts. In the words of Ryan Bozis, learn these functional constructs, and you'll be able to program your very own forest. Being polyglot is good! Learning a new programming language broadens your thinking and provides you a competitive edge. Happy functional programming!

What this book covers

Chapter 1, Embrace the Truth, explains F#'s rather special role in the functional programming world. You will also discuss F#'s roots in ML, the context in which F# works, that is, running on top of .NET stack, compiled to IL, utilizing BCL and the hybrid nature of the languages.

Chapter 2, Now Lazily Get Over It, Again, will prepare you to delve into the intermediate F# concepts which you are going to utilize later. It will help you in setting up the Visual Studio .NET and F# Compiler to work together along with the environment and runtime, review how to run your F# programs in IDE and through interactive REPL shell, implement the Fibonacci sequence and Tower of Hanoi using recursion, and apply lazy evaluation for quick sort.

Chapter 3, What's in the Bag Anyway?, will provide insights about the built-in data structures—array, list, set, and map, and will present their typical use cases.

Chapter 4, Are We There Yet?, delves into sequence expression (seq), implementation of custom enumeration for purpose of sequence expression (that is, paging functionality), and application of simple custom types using records, tuples.

Chapter 5, Let's Stack Up, will help you build a basic ADT of a stack using F#, implement the fundamental operations, and proceed to make a concurrent version of a stack. You will also learn how to do unit testing in C# for an F# program and implement the same test method in F#.

Chapter 6, See the Forest for the Trees, will explain graph related algorithms, and teach you the implementation of your own trees. You will also learn to tackle tree searching and various other traversal techniques.

Chapter 7, Jumping the Queue, discusses the custom functional implementation of a queue. You will then be introduced to the FSharpX open source collection of functional data structures. Finally, you will explore the F# agent of MailboxProcessor, for creating async work flows, throttling, and post-processing of the results of asynchronous calls as an example usage of a queue.

Chapter 8, Quick Boost with Graph, will briefly discuss how a graph can be implemented in a functional language, and why it is a rather difficult task to undertake. You will then discover some commonly used graph implementations and explore one of the most typical shortest path graph implementation, Dijkstra.

Chapter 9, Sets, Maps, and Vectors of Indirections, reviews sets and maps, and explores a custom implementation of a vector. Additionally, you are going to discuss Intermediate Language and how it works in the .NET ecosystem.

Chapter 10, Where to Go Next?, is a reference chapter in which you can acquaint yourself with the detailed list of different resources around the functional eco-system, and the F# programming language. You will also find various guides, source code and links, which will assist you in getting additional information you will need to polish your knowledge about F#.

What you need for this book

To get started with working on F#, you will need Visual Studio 2013. Also, you will need Windows or Linux/MacOS with Mono to build the server, console and GUI applications. Visual Studio 2013 Professional/Community Edition is preferred.

Who this book is for

If you have just started your adventure with F#, then this book will help you take the right steps to become a successful F# programmer, thereby improving your current development skills. Intermediate knowledge of imperative programming concepts and a basic understanding of the algorithms and data structures in .NET environments using the C# language and BCL (Base Class Library) would be helpful.

Conventions

In this book, you will find a number of text styles that distinguish between different kinds of information. Here are some examples of these styles and an explanation of their meaning.

Code words in text, database table names, folder names, filenames, file extensions, pathnames, dummy URLs, user input, and Twitter handles are shown as follows: " You can also use the #help;; directive to list other directives inside FSI."

A block of code is set as follows:

val cubeMe : x:int -> int
> > cubeMe 9;;
val it : int = 729

Any command-line input or output is written as follows:

square 10;;
^^^^^^
error FS0039: The value or constructor 'square' is not defined

New terms and important words are shown in bold. Words that you see on the screen, for example, in menus or dialog boxes, appear in the text like this: "When this function is executed in F# interactive, you can immediately see the results upon invocation as in the following screenshot."

Note

Warnings or important notes appear in a box like this.

Tip

Tips and tricks appear like this.

Reader feedback

Feedback from our readers is always welcome. Let us know what you think about this book—what you liked or disliked. Reader feedback is important for us as it helps us develop titles that you will really get the most out of.

To send us general feedback, simply e-mail <feedback@packtpub.com>, and mention the book's title in the subject of your message.

If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, see our author guide at www.packtpub.com/authors.

Customer support

Now that you are the proud owner of a Packt book, we have a number of things to help you to get the most from your purchase.

Downloading the example code

You can download the example code files from your account at http://www.packtpub.com for all the Packt Publishing books you have purchased. If you purchased this book elsewhere, you can visit http://www.packtpub.com/support and register to have the files e-mailed directly to you. The GitHub repository for the code files are also available at https://github.com/adnanmasood/Learning-fsharp.

Errata

Although we have taken every care to ensure the accuracy of our content, mistakes do happen. If you find a mistake in one of our books—maybe a mistake in the text or the code—we would be grateful if you could report this to us. By doing so, you can save other readers from frustration and help us improve subsequent versions of this book. If you find any errata, please report them by visiting http://www.packtpub.com/submit-errata, selecting your book, clicking on the Errata Submission Form link, and entering the details of your errata. Once your errata are verified, your submission will be accepted and the errata will be uploaded to our website or added to any list of existing errata under the Errata section of that title.

To view the previously submitted errata, go to https://www.packtpub.com/books/content/support and enter the name of the book in the search field. The required information will appear under the Errata section.

Piracy

Piracy of copyrighted material on the Internet is an ongoing problem across all media. At Packt, we take the protection of our copyright and licenses very seriously. If you come across any illegal copies of our works in any form on the Internet, please provide us with the location address or website name immediately so that we can pursue a remedy.

Please contact us at <copyright@packtpub.com> with a link to the suspected pirated material.

We appreciate your help in protecting our authors and our ability to bring you valuable content.

Questions

If you have a problem with any aspect of this book, you can contact us at <questions@packtpub.com>, and we will do our best to address the problem.