Learning Functional Programming Managing Code Complexity by Thinking Functionally (Jack Widman) (Z Library)

📄 File Format: PDF

💾 File Size: 2.6 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

Lea rning Functiona l Prog ra m m ing Lea rning Functiona l Prog ra m m ing Jack Widman Learning Functional Programming Managing Code Complexity by Thinking Functionally

📄 Page 2

SOF T WARE DEVELOPMENT “This book highlights the beauty and safety of functional programming. It clarified topics that I have long only loosely understood, and inspires me to begin practicing more functional programming techniques in my professional work.” —Matthew Campagna, PhD Sr. Principal Engineer, Amazon Web Services Learning Functional Programming US $59.99 CAN $74.99 ISBN: 978-1-098-11175-5 Twitter: @oreillymedia linkedin.com/company/oreilly-media youtube.com/oreillymedia Learn how to think and write code like a functional programmer. With this practical guide, software developers familiar with object-oriented programming will dive into the core concepts of functional programming and learn how to use both functional and OOP features together on large or complex software projects. Author Jack Widman uses samples from Java, Python, C#, Scala, and JavaScript to help you gain a new perspective and a set of tools for managing the complexity in your problem domain. You’ll be able to write code that’s simpler, reusable, easier to test and modify, and more consistently correct. This book also shows you how to use patterns from category theory to help bridge the gap between OOP and functional programming. • Learn functional programming fundamentals and explore the way functional programmers approach problems • Understand how FP differs from object-oriented and imperative programming • Use a set of practical, applicable design patterns that model reality in a functional way • Learn how to incorporate FP and OOP features into software projects • Apply functional design patterns appropriately and use them to write correct, robust, and easily modifiable code Jack Widman has more than 20 years of experience writing software. He provides consulting services to a wide range of software teams, especially with respect to converting codebases to a functional style of coding. Jack has a PhD in mathematics from Wesleyan University as well as a deep knowledge and a passion for software.

📄 Page 3

Jack Widman, PhD Learning Functional Programming Managing Code Complexity by Thinking Functionally Boston Farnham Sebastopol TokyoBeijing

📄 Page 4

978-1-098-11175-5 [LSI] Learning Functional Programming by Jack Widman, PhD Copyright © 2022 Jack Widman. All rights reserved. Printed in the United States of America. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. O’Reilly books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (http://oreilly.com). For more information, contact our corporate/institutional sales department: 800-998-9938 or corporate@oreilly.com. Acquisitions Editor: Mary Preap Development Editor: Shira Evans Production Editor: Kate Galloway Copyeditor: Justin Billing Proofreader: Stephanie English Indexer: nSight, Inc. Interior Designer: David Futato Cover Designer: Karen Montgomery Illustrator: Kate Dullea August 2022: First Edition Revision History for the First Edition 2022-08-11: First Release See http://oreilly.com/catalog/errata.csp?isbn=9781098111755 for release details. The O’Reilly logo is a registered trademark of O’Reilly Media, Inc. Learning Functional Programming, the cover image, and related trade dress are trademarks of O’Reilly Media, Inc. The views expressed in this work are those of the author, and do not represent the publisher’s views. While the publisher and the author have used good faith efforts to ensure that the information and instructions contained in this work are accurate, the publisher and the author disclaim all responsibility for errors or omissions, including without limitation responsibility for damages resulting from the use of or reliance on this work. Use of the information and instructions contained in this work is at your own risk. If any code samples or other technology this work contains or describes is subject to open source licenses or the intellectual property rights of others, it is your responsibility to ensure that your use thereof complies with such licenses and/or rights.

📄 Page 5

To my three wonderful daughters: Katherine, Annie, and Victoria. And to Andrea, whose support and love have encouraged me in so many ways.

📄 Page 6

(This page has no text content)

📄 Page 7

Table of Contents Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1. What Is Functional Programming?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Immutability 2 Referential Transparency 5 Higher Order Functions 7 Lazy Evaluation 8 Thinking Like a Functional Programmer 9 The Benefits of FP 10 FP Can Improve Productivity 11 FP Is Fun! 11 Scala 12 Conclusion 13 2. Mathematical Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Set Theory 15 Functions 16 Kinds of Functions 18 Computer Science Fundamentals 20 Anonymous Functions 20 Functions as First Class Objects 21 Conclusion 21 3. Category Theory and Patterns. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Category Theory–Based Patterns 25 A Brief History 26 Objects and Morphisms 26 An Example of a Category 27 v

📄 Page 8

The Category Scal 31 Functors 33 Programming Language Formulation of a Functor 35 The Patterns 37 The Functor Pattern 38 Monoids 39 Natural Transformations 41 Monads 43 Conclusion 45 4. Functional Data Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 The Option Data Structure 48 The Try Data Structure 52 The Either Data Structure 52 Higher Order Functions 54 Monads in for Comprehensions in Scala 55 Traditional Data Structures 57 Immutability and History 57 Laziness 58 Conclusion 58 5. More on Immutability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Mutable and Immutable Variables 59 Recursion 60 A Linked List Example 61 Tail Recursion 66 More Examples of the Power of fold in Scala 70 A Connection Between fold and Monoids 71 More with Higher Order Functions 74 From map to flatMap 76 Conclusion 77 6. Questions of Concurrency. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 Streams 83 Akka Streams 83 Source 83 Flow 84 Sink 85 More on Streams 85 FS2: Functional Streams for Scala 86 Conclusion 88 vi | Table of Contents

📄 Page 9

7. Where to from Here?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Taking the Pure Route 89 The IO Monad 91 Taking the Middle Route 93 JVM Languages 93 .NET Languages 94 Type Classes 94 Conclusion 99 Appendix. Scala. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Table of Contents | vii

📄 Page 10

(This page has no text content)

📄 Page 11

Preface Over the past few years, functional programming (FP) has been experiencing a renaissance. Many companies are looking for programmers with experience in FP, as languages that were not originally designed to be functional have evolved over time to include functional capabilities: languages such as Java, JavaScript, and Python, to name a few. The push for programmers with functional experience is due, in part, to a perceived improvement in the development process, including a sense that fewer bugs are produced and more extensible and robust code is produced when following the functional way. Whether this is true or not—and whether a greater percentage of the code written in the coming years is functional—will become evident in time. For now, let us consider FP one of a number of paradigms, each with its own pros and cons. Who Should Use This Book? Essentially, all programmers. If you have no experience in FP, but have heard about it and you are curious, or even if you picked up this book in a store without any knowl‐ edge of FP, this book will prove useful to you. Experienced FP programmers too, will find something to benefit them. The book dives into the category theory roots of FP in a way not presented in other books on this subject. Finally, programmers with some experience using FP but who want to gain a more advanced understanding of the concepts and theory that make up FP will find much to use and enjoy. How The Book Is Organized I endeavor to demonstrate, through various programming languages, how functional constructs can improve our code. However, you will notice that Scala is the frequent language of choice for code examples due to the ease with which functional ideas can be expressed in Scala; the reader will more easily appreciate and understand the functional ideas when they are expressed in the natural way, which Scala allows. For a mini-introduction to Scala, see the Appendix. ix

📄 Page 12

Conventions Used in This Book The following typographical conventions are used in this book: Italic Indicates new terms, URLs, email addresses, filenames, and file extensions. Constant width Used for program listings, as well as within paragraphs to refer to program elements such as variable or function names, databases, data types, environment variables, statements, and keywords. This element signifies a tip or suggestion. This element signifies a general note. This element indicates a warning or caution. O’Reilly Online Learning For more than 40 years, O’Reilly Media has provided technol‐ ogy and business training, knowledge, and insight to help companies succeed. Our unique network of experts and innovators share their knowledge and expertise through books, articles, and our online learning platform. O’Reilly’s online learning platform gives you on-demand access to live training courses, in-depth learning paths, interactive coding environments, and a vast collection of text and video from O’Reilly and 200+ other publishers. For more information, visit http://oreilly.com. x | Preface

📄 Page 13

How to Contact Us Please address comments and questions concerning this book to the publisher: O’Reilly Media, Inc. 1005 Gravenstein Highway North Sebastopol, CA 95472 800-998-9938 (in the United States or Canada) 707-829-0515 (international or local) 707-829-0104 (fax) We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at https://oreil.ly/learning-fp. Email bookquestions@oreilly.com to comment or ask technical questions about this book. For news and information about our books and courses, visit https://oreilly.com. Find us on LinkedIn: https://linkedin.com/company/oreilly-media. Follow us on Twitter: https://twitter.com/oreillymedia. Watch us on YouTube: https://youtube.com/oreillymedia. Preface | xi

📄 Page 14

(This page has no text content)

📄 Page 15

CHAPTER 1 What Is Functional Programming? Functional programming? Functors? Monoids? Monads? “I’m not a mathematician!” you might say. How can I learn these esoteric concepts? And why would I want to? These concerns are totally understandable. But the truth is you don’t need to be a mathematician to be a functional programmer. The fundamental concepts of FP are easy to understand when presented in a clear, straightforward way. And that is what this book is about. Making FP understandable and practical. In particular, I will teach you how to think like a functional program‐ mer. But why would you want to learn FP? Picture this. It’s 10 p.m. and you are totally stuck while trying to fix a bug in a program you need to submit in the morning. The problem seems to be centered around a variable called ratio. The problem is that depending on the state of the system you are modeling, the variable ratio keeps changing. Your frustration builds. Or you have a deadline at work and there is an elusive bug in your microservice that you are chasing down. The problem seems to be in two nested for loops in which variables are modified in a fairly complex way. The logic is complex and you don’t quite see the solution. If only there were a way to write programs in a way in which the value of variables would not change! FP to the rescue. Variables whose values change often are a considerable source of bugs in programs. It can be difficult to keep track of the value of the variable since it can change at any moment. So, what is FP? What makes one language functional and another not functional? The truth is that to some extent it is a matter of degree. You don’t have to follow every principle that falls under the heading of FP. Some people will try to follow all of them, 1

📄 Page 16

and others will pick and choose. It is totally up to you. FP is a paradigm, an approach to programming, a way of breaking up the world and putting it back together in code. It involves both how we organize that piece of the world we are modeling and how we organize and structure the code. To better describe the essence of FP, let us begin by contrasting it with imperative programming and object-oriented programming (OOP). There are others, such as logic programming, but the three mentioned are by far the most popular. Imperative is what you might think of as plain old programming. It’s what program‐ ming was before OOP and FP. In imperative programming, you write functions or procedures, use for and while loops, and mutate state often. Languages like C or Pascal are typical imperative programming languages. Then there is OOP. Currently the most popular paradigm, OOP is a process of modeling the world as a collection of objects. Each object has state and methods, which are operations representing behaviors specific and relevant to that object. As the program runs, the state of the objects changes. The benefits of this approach include encapsulation, which means the state and methods that belong to an object exist, at the code level, within the object. This is a much better idea than letting the state be scattered all throughout the code because managing mutable state is just plain difficult. You have multiple variables and their values are changing. The approach of FP is to acknowledge this and attempt to minimize, if not erradicate, changing state altogether. Eradicating changing state, rather than attempting to manage it, is a fundamental principal in FP. Ultimately, it is not always possible to avoid having mutable state, so the standard FP approach is to isolate the part of the code that mutates state. When we cannot eradicate all changing state, we can at least localize the code with the changing state into one place. Immutability The single most important aspect of FP is immutability. Generally speaking, this means a lack of change. Something is considered immutable if we cannot modify it in some way. In FP, this means a few things. Once a variable is set, its value cannot be changed. If x = 3 at the beginning of a program, it has that value for the remainder of the program. Does that mean that if a program is written in a functional style, and a person’s age changes, this change cannot be modeled? Of course not. That would be absurd. There are techniques like efficient copying that allow us to manipulate our 2 | Chapter 1: What Is Functional Programming?

📄 Page 17

1 In FP, all functions should return a value. void is a sure sign of side effects. code without ever mutating state. Consider the following simple for loop in Java that prints the numbers 0 to 99. Java for (int i = 0; i < 100; i++) { System.out.println( i ); } This type of code occurs all the time. You might wonder how we could possibly express this in an immutable way. It seems that the essence of this code is the changing of the value of the variable i. A common approach in FP is to use recursive functions; a recursive function is one that calls itself. In the case of the preceding code, you can put the code in a function and then call the function on the next value of i in each iteration. It might look something like the following: Java void f(int i) { if (i > 99) { return; } else { System.out.println( i) return f(i+1) } } f(0) Now this code is a little longer, but it does not mutate any state. If you know a little about FP, you might know that the return type void is a sure giveaway that there will be side effects.1 A side effect is anything that affects the program outside of the function. Things like writing to a file, throwing an exception, or modifying a global variable. The earlier code example is meant to show a single way of avoiding the mutation of state. You have probably been mutating state your whole programming career and it likely seems indispensable. But remember two things: • It feels very natural to mutate state • Mutating state is a major cause of code complexity The good news is that with practice, the FP way will feel just as natural. Immutability | 3

📄 Page 18

Let us consider another technique for avoiding the mutation of state. Imagine you have an object with a property or field that changes. The question here is how to model this situation without mutating a variable in the code. Let us consider a Java example first. Java public class Person { private final String name; private final int age; public Person(String name, int age) { this.name = name; this.age = age; } public static void main(String[] args) { Person person = new Person("Carl", 32); //A year passes Person changedPerson = new Person("Carl", 33); System.out.println(changedPerson); } } Instead of modifying the value of age in the Person object, we create a new object and initialize the new age value in the constructor. Let us now look at an example in Python. Python class Person: def __init__(self,name,age): self.name = name self.age = age def main(): person = Person("John",22) #One year later changedPerson = Person("John",23) One year passes and we need the Person object to reflect this. But we can’t modify the value age. So we create another immutable object with the age variable initialized to 23. Now let’s look at an example in Scala. 4 | Chapter 1: What Is Functional Programming?

📄 Page 19

Scala case class Person(name: String, age: Int) val person = Person("Katherine", 25) val changedPerson = person.copy(age=26) Declare a case class. Create an instance of the class. This line makes a new instance of Person and initializes age to 26. No state has been mutated. Immutability is one of the most important aspects of FP. Having a lot of mutable state in a program results in a lot of bugs. It’s simply not easy to keep track of all the changing values. Here, we have seen some examples of how to get around the apparent need to mutate state. It takes some getting used to but with a little practice, using these techniques may even start to seem natural. Referential Transparency The next crucial component of FP is referential transparency. We say an expression is referentially transparent if we can replace it with its value anywhere in the code. You might think, upon first hearing about this, that you can always do this. Let us consider a simple example of a nonreferentially transparent function. Java today() If I call this function, get May 29th, 2021, replace its body with this value, and then call it tomorrow, I will get the wrong answer. So the today function is not referentially transparent. Here are a couple more examples of nonreferential transparency: • A function that returns a random number. Obviously you can’t replace the body of the function with a value you get when you call it once. • A function that throws an exception. Exceptions are generally avoided in FP. I will come back to this later. It probably seems that if we throw out all nonreferentially transparent functions (and that is what we will aim for), that we will lose some valuable capabilities—that perhaps we will be unable to express certain useful things. Rest assured, there are functional ways of expressing these things. Referential Transparency | 5

📄 Page 20

2 This is meant to be a joke, but I’ve experienced these reactions firsthand. A related concept that you will see in writings about FP is purity. Unfortunately, there is some confusion in the literature about the relationship between purity and referential transparency and not everybody agrees on the meanings of these terms. Generally, a function is said to be pure if it has no side effects and for a given input, always returns the same output. This basically means that if the input is x and the output is y, no matter how many times you call the function with x as the input parameter, the function will return y. A side effect is anything that happens outside of the context of the function. Writing to a file and throwing an exception are two examples of side effects. Forget for the moment that we need to write to files (though arguably we don’t need to throw exceptions), and think how nice it would be if every time we call a function with the same input parameters, we get the same output and nothing outside of the function is changed. That is something we enjoy in FP. In FP, we strive to use only pure functions. That is, functions that have no side effects and have the property that if you supply the same input, you get the same output. Because different people have different views on this, and because the differences between referential transparency and purity are subtle, I will treat the two terms as synonymous. Now, I said you don’t have to be a mathematician to write functional programs, and you don’t. But FP does come from mathematics. It comes from two fields, actually, lambda calculus and category theory. Category theory has much to do with functions. And in mathematics, functions are pure. When a programmer looks at an expression like x = x + 1, they say, “Ah, increment the variable.” When a mathematician looks at x = x + 1, they say, “No, it doesn’t.”2 Now what would an impure function look like? Scala object Main extends App { def impureFunction(x: Int): Int = { import scala.util.Random return Random.nextInt(100) + x } println(impureFunction(5)) println(impureFunction(8)) } 6 | Chapter 1: What Is Functional Programming?