32,39 €
Mehr erfahren.
- Herausgeber: Packt Publishing
- Kategorie: Fachliteratur
- Sprache: Englisch
If you have just started your adventure with F#, then this book will help you take the right steps to become a successful F# coder. An 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.
Das E-Book können Sie in Legimi-Apps oder einer beliebigen App lesen, die das folgende Format unterstützen:
Seitenzahl: 240
Veröffentlichungsjahr: 2015
Ähnliche
Table of Contents
Learning F# Functional Data Structures and Algorithms
Learning F# Functional Data Structures and Algorithms
Copyright © 2015 Packt Publishing
All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.
Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing, and its dealers and distributors will be held liable for any damages caused or alleged to be caused directly or indirectly by this book.
Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.
First published: June 2015
Production reference: 1240615
Published by Packt Publishing Ltd.
Livery Place
35 Livery Street
Birmingham B3 2PB, UK.
ISBN 978-1-78355-847-6
www.packtpub.com
Credits
Author
Adnan Masood, Ph.D.
Reviewers
Steve Bearman
Taha Hachana
Marcin Juraszek
Rohit Pathak
Commissioning Editor
Kunal Parikh
Acquisition Editor
Shaon Basu
Content Development Editor
Rahul Nair
Technical Editor
Parag Topre
Copy Editors
Relin Hedly
Sonia Mathur
Project Coordinator
Nidhi Joshi
Proofreaders
Stephen Copestake
Safis Editing
Indexer
Monica Ajmera Mehta
Graphics
Disha Haria
Jason Monteiro
Production Coordinator
Nilesh R. Mohite
Cover Work
Nilesh R. Mohite
Foreword
Functional programming is about to become mainstream, and learning F# helps a programmer build skills in multiple paradigms. It doesn't surprise me at all that Adnan has found his way to functional programming. His dedication to technological excellence is expressed eloquently in this book, and if you want to get started with F#, this is the book to read.
Jon Flanders
Pluralsight Trainer, Microsoft MVP
Foreword
In the era of multiprocessor and multimachine processing, functional principles are becoming increasingly important for modern programmers. For those developing in the Microsoft ecosystem, F# is a functional first multiparadigm language that allows practitioners to apply these principles in a truly powerful way. As developers become more familiar with functional data structures and the algorithms that use them truly safely, by extension, powerful software will become a more commonplace commodity that will drive the next era of technological innovation. I can't think of a more thorough and thoughtful person to help guide us through these principles than Adnan. Enjoy!
Seth Juarez
Senior Technical Evangelist, Microsoft
Foreword
F# is a functional and object-oriented programming language with the power of the .NET Framework. This language has gained huge popularity among a broad range of programmers. With a focus on writing simple code to solve complex problems, F# is being used by data scientists, enterprise developers, and enterprise enthusiasts. In fact, its popularity has increased so much in recent times that according to the TIOBE index (ranked 11th as of March 2015), F# is all set to gain an esteemed position among the top 10 programming languages.
With the rise in interest and usage around F#, it's bound to continue to attract the attention of hobbyists who want to try out writing programs with F#. I am very excited about Adnan Masood's efforts and appreciative of his work, which focuses on the basics of functional programming, data structures, and algorithms. Adnan has followed a very structured approach to take you on a journey where you can discover and familiarize yourself with this powerful multiparadigm programming language. Starting with setting the context and discussing the basics of F# programming, Adnan gradually moves on to a more detailed and increasingly focused conversation surrounding data structures and algorithms. He also covers approaches related to testing bespoke data structures and algorithms. Towards the end, Adnan covers the implementation of modern and complex abstract data types (ADTs) and highlights how to use parallel programming and asynchrony within the F# setting.
I highly recommend this book and ask you to focus your energies on learning this amazing and powerful multiparadigm, open source, and cross-platform programming language. This book will help you tackle computing problems with a simple, maintainable, and robust code.
Happy F# Programming.
Hammad Rajjoub
Architect Advisor, Mobility Lead (Asia), Microsoft
About the Author
Adnan Masood, Ph.D. is a developer, software architect, and researcher and specializes in machine learning and Bayesian belief networks. He is an avid engineer and is most comfortable working with the IDE. Before joining Green Dot Corporation, a leading prepaid financial technology institution, he enjoyed life as a principal engineer of a start-up and worked for a leading UK nonprofit organization as a solutions architect.
A strong believer in the development community, Adnan is an active member of the Open Web Application Security Project (OWASP), an organization dedicated to software security. In the .NET community, he is a cofounder and president of the Pasadena .NET Developers group, which he has been successfully leading for 8 years. He pursues interests in algorithmic puzzles, machine learning, functional programming, cloud computing, service-oriented architecture (SOA), .NET, design patterns, application security, and robotics. He has also led a number of successful enterprise solutions and consulted for several Fortune 500 company projects.
Adnan devotes himself to his own continual, practical education. He holds certifications in big data, machine learning, and systems architecture from Massachusetts Institute of Technology; an Application Security certification from Stanford University; an SOA Smarts certification from Carnegie Mellon University; and certifications as a ScrumMaster, Microsoft Certified Trainer, Microsoft Certified Solutions Developer, and Sun Certified Java Developer.
Adnan has taught Windows Communication Foundation (WCF) courses at the University of California, San Diego, and loves to conduct presentations at top academic and technology conferences (for example, IEEE-HST, IASA, and DevConnections), local code camps, and user groups. He is also a volunteer FLL robotics coach for middle school students at Universal Academy of Florida.
At home, his two very energetic boys, Zakariya and Ali, keep him busy—but not quite busy enough to keep him from compulsively buying (though not always reading) books in all formats. Adnan defines Pluto as a planet, chocolate as a food group, and A Game of Thrones as historical fiction.
For more details, visit Adnan's blog (http://blog.adnanmasood.com), GitHub repository (http://github.com/adnanmasood), and Twitter (@adnanmasood). Adnan can be reached at <[email protected]>.
Acknowledgments
I am very grateful to the technical reviewers—Steve Bearman, Taha Hachana, Marcin Juraszek, and Rohit Pathak—whose meticulous reviews proved invaluable in improving the quality of this book. Thank you for your diligence and your help throughout the process. Thanks to the excellent team at Packt Publishing. I would also like to thank the technical editor, Parag Topre, and the content development editor, Rahul Nair, who worked with me and kept this project on track to publish this book. Your assistance as an editor and reviewer along with your comments were invaluable in ensuring that this book was a comprehensive and reliable source of information on F# and functional programming.
Thanks to Don Syme and Microsoft Research, without whom neither F# nor this book would have been possible, and to the excellent F# community that provides plenty of resources. It has been my privilege to work closely with Jeff Bergman (Google), who got me started on F# and functional programming. I am forever grateful to Stephen Soong, for his unwavering support and feedback, and David Lazar, who allowed me to run seemingly crazy ideas by him. I am indebted to all my friends and colleagues, including Nicolas Naaman, David Gullett, Calvin Park, Teresa Watkins, Raja Peer, Dave Banta, Ajit Kumar, Dr. Jevdet Rexhepi, Paul Watson, Dr. John Dean, Kamran Masood, Jim Java, Muhammad Mansoor, Antony Chhan, Rashid Kamran, Jeff Cox, Mobeen Minai, Rob Walling, and Kamran Zameer, to name a few, for reading the early drafts and providing feedback and encouragement. And last but not least, special thanks to my family for their support and to my kids, Zakariya and Ali; without their shenanigans, this book would have been finished 6 months earlier. Love you guys!
About the Reviewers
Steve Bearman is a software developer with his own software and consulting company, Suzy B Studios. He supports all sectors from science and engineering through business and finance and specializes in the thorny, complex problems where architecture, algorithms, performance, and usability are critical. He has been developing with .NET for over a decade. He has long been functionally oriented; one of his first preferred programming languages, years ago, was the early functional, mathematical programming language APL.
Steve has a special fondness for good algorithms and appropriate technology. He has taught university graduate-level computer science and managed marketing and operations as the VP of a manufacturing corporation. Steve has published technical papers dealing with data, its analysis, interpretation, and automated collection. He speaks frequently on technical topics. He has an SB in Mathematics from MIT and an MA in applied mathematics, concentrating on algorithms and mathematical statistics, from the University of California, San Diego.
He enjoys life with his beautiful wife and two dogs, holds black belts in two styles of martial arts, juggles, rides his unicycle, and enjoys the arts and the outdoors.
Taha Hachana is an enthusiast F# hacker. He has been using this language since 2008 (2 years before it became a Microsoft product). As an active community member, he has been maintaining several open source F# projects on GitHub, focusing on web development with the WebSharper framework and data visualization. When he's not coding, Taha enjoys practicing martial arts and yoga. You can follow him on Twitter at @TahaHachana and read his blog at http://fsharp-code.blogspot.com/.
Marcin Juraszek is a software engineer at Microsoft. He is associated with Office Online, a web browser-based version of the Microsoft Office productivity suite.
He holds bachelor's of engineering and master's of science degrees in computer science from the Silesian University of Technology in Gliwice, Poland. Before moving to the U.S., Marcin worked at Future Processing, one of the fastest growing software companies in central and eastern Europe.
He has been a .NET developer since the last 4 years. His expertise spans across most of .NET stack, including C#, VB.NET, F#, ASP.NET, XAML, WPF, Silverlight, LINQ, and .NET Core. He's also interested in new technologies, such as TypeScript, Azure, Roslyn, and so on.
He runs his own programming-oriented blog at http://marcinjuraszek.com and is an active member of the Stack Overflow community.
Rohit Pathak has a degree in computer science from Rajiv Gandhi Technical University. He picked up his interest in functional programming while working on High Performance Computing (HPC) at AITR (Acropolis Institute of Technology and Research). For years, he worked at Innovation at Incubation Labs and NTI (NEC Technologies India Limited), focusing on machine learning, static model checking, compilers, and HPC. Currently, he is working as a lead software engineer with the system and verification group at Cadence Design Systems.
www.PacktPub.com
Support files, eBooks, discount offers, and more
For support files and downloads related to your book, please visit www.PacktPub.com.
Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.PacktPub.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at <[email protected]> for more details.
At www.PacktPub.com, you can also read a collection of free technical articles, sign up for a range of free newsletters and receive exclusive discounts and offers on Packt books and eBooks.
https://www2.packtpub.com/books/subscription/packtlib
Do you need instant solutions to your IT questions? PacktLib is Packt's online digital book library. Here, you can search, access, and read Packt's entire library of books.
Why subscribe?
Free access for Packt account holders
If you have an account with Packt at www.PacktPub.com, you can use this to access PacktLib today and view 9 entirely free books. Simply use your login credentials for immediate access.
Preface
"If there's a book that you want to read, but it hasn't been written yet, then you must write it."
--Toni MorrisonF# 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 individual 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.
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 <[email protected]>, 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 <[email protected]> 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 <[email protected]>, and we will do our best to address the problem.
Chapter 1. Embrace the Truth
"Object oriented programming makes code understandable by encapsulating moving parts. Functional programming makes code understandable by minimizing moving parts."
--Michael FeathersThe history of functional programming can be traced back to the Church and Rosser's original work on Lambda Calculus in 1936 and yet, the concepts and implementation of this important programming paradigm are somehow limited to academia while its object-oriented and imperative counterpart dominates the industry. Good news is, this trend is changing fast! With the functional paradigm support in modern programming languages, such as Scala, Clojure, F#, Ruby, and to some extent, the omnipresent JavaScript, the benefits of functional programming are being realized. The increased use of some classical functional languages, such as OCaml, Erlang, Scheme, and Lisp in high-concurrency environments has led to realization of the functional advantages of brevity, terseness, scalability and performance.
In this chapter, we will cover everything that a hobbyist F# developer, who is just starting his/her adventure in functional programming, needs to know in order to be able to follow the discussion through rest of the book. We will begin with a short explanation of F# language's rather special role in the functional programming world, and will explain why it isn't strictly a functional programming language. Throughout the book, and in this chapter particularly, we will address the historic sketches of functional languages and their predecessors. We will discuss F# language'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. You will see several new terms used in this and the following chapters; these terms will have a cursory definition, but will be elaborated on as we discuss these topics in detail during subsequent chapters.
By the end of this chapter, you will be familiar with a brief history of functional programming. With comparative code examples, we will analyze code samples using mutable, and immulatable data structures as well as imperative control flow syntax that will allow you, the reader, to fully understand and embrace the hybrid nature of F#.
In this chapter, we will cover the following topics:
Exploring the functional programming paradigm
There is no universally accepted definition of functional programming, and any attempt to do so usually results in seemingly infinite stack overflow/Reddit comment threads, flame-wars, and eventually hate-mail. The following are the most agreed upon attributes of a functional programming language:
