Tài liệu Functional python programming

Functional Python Programming Create succinct and expressive implementations with functional programming in Python Steven Lott BIRMINGHAM - MUMBAI Functional Python Programming 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: January 2015 Production reference: 1270115 Published by Packt Publishing Ltd. Livery Place 35 Livery Street Birmingham B3 2PB, UK. ISBN 978-1-78439-699-2 www.packtpub.com Credits Author Steven Lott Copy Editors Roshni Banerjee Pranjali Chury Reviewers Oleg Broytman Rui Carmo Ian Cordasco Julien Danjou Amoatey Harrison Deepa Nambiar Karuna Narayanan Nithya P Project Coordinator Danuta Jones Shivin Kapur Gong Yi Commissioning Editor Ed Gordon Acquisition Editor Owen Roberts Content Development Editor Sumeet Sawant Technical Editor Abhishek R. Kotian Proofreaders Stephen Copestake Maria Gould Bernadette Watkins Indexer Hemangini Bari Graphics Abhinash Sahu Production Coordinator Melwyn D'sa Cover Work Melwyn D'sa About the Author Steven Lott has been programming since the 1970s, when computers were large, expensive, and rare. As a contract software developer and architect, he has worked on hundreds of projects, from very small to very large. He's been using Python to solve business problems for over 10 years. He's particularly adept struggling with gnarly data representation problems. His other titles include Mastering Object-Oriented Python and Python for Secret Agents, both by Packt Publishing. After spending years as a technomad—living in various places on the east coast of the US—he has dropped the hook in the Chesapeake Bay. He blogs at http://slott-softwarearchitect. blogspot.com. About the Reviewers Oleg Broytman is a software developer currently working with web technologies on Unix/Linux using the Python programming language on the server side and Javascript on the client side. Oleg started to work with computers even before the IBM PC era. He worked with DOS for some time and then switched to Unix, mostly Linux and FreeBSD. For about 25 years, he has been working in the medicine field in Moscow, Russia. You can contact him at [email protected]. I'd like to thank my wife Olga! She supports everything I do any way I do it (well, mostly!). Her love and support make me happy and allow me to achieve as much as I do. Rui Carmo is a systems architect with 20 years' experience in telecoms and Internet, having worked in software development, product management, mobile network planning, systems engineering, virtualization, cloud services, and a lot of what the industry is currently trying to roll into the "DevOps" moniker. He has been coding in Python for over a decade (starting with Python 2.3) and has gravitated towards Clojure, Erlang, and Hy (an LISP that leverages the Python AST) in the past few years due to the intrinsic advantages of functional programming. He currently lives in the wonderful city of Lisbon, Portugal, with his wife and two children, and he blogs at http://taoofmac.com. You can find him on GitHub, Twitter, and Hacker News as @rcarmo. Julien Danjou is an open source hacker working at Red Hat. He started his career as a Debian developer and contributed to a lot of free software (GNU Emacs, Freedesktop, and so on), writing some software on his own, such as the awesome window manager. Nowadays, Julien contributes to OpenStack, an open source cloud platform entirely written in Python. He has been a Python developer since then, worked on Hy (an LISP dialect in Python), and written a self-published book titled The Hacker's Guide to Python in 2014. Amoatey Harrison is a Python programmer with a passion for building software systems to solve problems. When he is not programming, he is playing video games, swimming, or simply hanging out with friends. After graduating from the Kwame Nkrumah University of Science and Technology with a degree in computer engineering, he is doing his national service at the GCB Bank Head Office in Accra, Ghana. He would like to think of himself as a cool nerd. Shivin Kapur is an aspiring computer science student who is passionate about learning new things. Gong Yi is a software developer working in Shanghai, China. He maintains an open source project at https://github.com/topikachu/python-ev3, which can control LEGO® MINDSTORMS® EV3 by Python language. I thank my wife Zhu Xiaoling for her patience and love, and I thank my son Yang Yang for being the best thing ever. 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? • Fully searchable across every book published by Packt • Copy and paste, print, and bookmark content • On demand and accessible via a web browser 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. Table of Contents Preface 1 Chapter 1: Introducing Functional Programming 9 Identifying a paradigm 10 Subdividing the procedural paradigm 11 Using the functional paradigm 12 Using a functional hybrid 14 Looking at object creation 15 The stack of turtles 16 A classic example of functional programming 17 Exploratory Data Analysis 20 Summary 22 Chapter 2: Introducing Some Functional Features 23 Chapter 3: Functions, Iterators, and Generators 37 First-class functions 24 Pure functions 24 Higher-order functions 25 Immutable data 26 Strict and non-strict evaluation 27 Recursion instead of a explicit loop state 29 Functional type systems 33 Familiar territory 34 Saving some advanced concepts 34 Summary 35 Writing pure functions Functions as first-class objects Using strings 38 39 41 Table of Contents Using tuples and namedtuples 42 Using generator expressions 43 Exploring the limitations of generators 46 Combining generator expressions 47 Cleaning raw data with generator functions 48 Using lists, dicts, and sets 50 Using stateful mappings 53 Using the bisect module to create a mapping 55 Using stateful sets 56 Summary 57 Chapter 4: Working with Collections 59 Chapter 5: Higher-order Functions 87 An overview of function varieties 60 Working with iterables 60 Parsing an XML file 61 Parsing a file at a higher level 63 Pairing up items from a sequence 65 Using the iter() function explicitly 67 Extending a simple loop 68 Applying generator expressions to scalar functions 71 Using any() and all() as reductions 73 Using len() and sum() 75 Using sums and counts for statistics 76 Using zip() to structure and flatten sequences 78 Unzipping a zipped sequence 80 Flattening sequences 80 Structuring flat sequences 81 Structuring flat sequences—an alternative approach 83 Using reversed() to change the order 84 Using enumerate() to include a sequence number 85 Summary 86 Using max() and min() to find extrema Using Python lambda forms Lambdas and the lambda calculus Using the map() function to apply a function to a collection Working with lambda forms and map() Using map() with multiple sequences Using the filter() function to pass or reject data Using filter() to identify outliers The iter() function with a sentinel value [ ii ] 88 91 93 93 94 95 96 98 99 Table of Contents Using sorted() to put data in order 100 Writing higher-order functions 101 Writing higher-order mappings and filters 101 Unwrapping data while mapping 103 Wrapping additional data while mapping 104 Flattening data while mapping 106 Structuring data while filtering 107 Writing generator functions 108 Building higher-order functions with Callables 111 Assuring good functional design 112 Looking at some of the design patterns 114 Summary 116 Chapter 6: Recursions and Reductions Simple numerical recursions Implementing tail-call optimization Leaving recursion in place Handling difficult tail-call optimization Processing collections via recursion Tail-call optimization for collections Reductions and folding – from many to one Group-by reductions – from many to fewer Building a mapping with Counter Building a mapping by sorting Grouping or partitioning data by key values Writing more general group-by reductions Writing higher-order reductions Writing file parsers Parsing CSV files Parsing plain text files with headers 117 118 119 120 121 122 123 124 126 127 128 130 132 133 135 137 138 Summary 140 Chapter 7: Additional Tuple Techniques 141 Using an immutable namedtuple as a record 142 Building namedtuples with functional constructors 145 Avoiding stateful classes by using families of tuples 145 Assigning statistical ranks 148 Wrapping instead of state changing 149 Rewrapping instead of state changing 150 Computing the Spearman rank-order correlation 152 Polymorphism and Pythonic pattern matching 153 Summary 158 [ iii ] Table of Contents Chapter 8: The Itertools Module 159 Chapter 9: More Itertools Techniques 181 Chapter 10: The Functools Module 197 Working with the infinite iterators 160 Counting with count() 160 Reiterating a cycle with cycle() 162 Repeating a single value with repeat() 164 Using the finite iterators 165 Assigning numbers with enumerate() 166 Running totals with accumulate() 167 Combining iterators with chain() 169 Partitioning an iterator with groupby() 170 Merging iterables with zip_longest() and zip() 171 Filtering with compress() 171 Picking subsets with islice() 172 Stateful filtering with dropwhile() and takewhile() 173 Two approaches to filtering with filterfalse() and filter() 175 Applying a function to data via starmap() and map() 176 Cloning iterators with tee() 177 The itertools recipes 178 Summary 179 Enumerating the Cartesian product 182 Reducing a product 182 Computing distances 184 Getting all pixels and all colors 185 Performance analysis 186 Rearranging the problem 188 Combining two transformations 189 Permuting a collection of values 190 Generating all combinations 191 Recipes 194 Summary 195 Function tools Memoizing previous results with lru_cache Defining classes with total ordering Defining number classes Applying partial arguments with partial() Reducing sets of data with reduce() Combining map() and reduce() Using reduce() and partial() [ iv ] 198 198 201 203 205 206 207 208 Table of Contents Using map() and reduce() to sanitize raw data 209 Using groupby() and reduce() 210 Summary 212 Chapter 11: Decorator Design Techniques 213 Chapter 12: The Multiprocessing and Threading Modules 229 Chapter 13: Conditional Expressions and the Operator Module 253 Decorators as higher-order functions 213 Using functool's update_wrapper() functions 216 Cross-cutting concerns 217 Composite design 218 Preprocessing bad data 219 Adding a parameter to a decorator 220 Implementing more complex descriptors 223 Recognizing design limitations 223 Summary 227 What concurrency really means 230 The boundary conditions 231 Sharing resources with process or threads 231 Where benefits will accrue 232 Using multiprocessing pools and tasks 233 Processing many large files 234 Parsing log files – gathering the rows 235 Parsing log lines into namedtuples 236 Parsing additional fields of an Access object 238 Filtering the access details 241 Analyzing the access details 243 The complete analysis process 244 Using a multiprocessing pool for concurrent processing 244 Using apply() to make a single request 247 Using map_async(), starmap_async(), and apply_async() 247 More complex multiprocessing architectures 248 Using the concurrent.futures module 248 Using concurrent.futures thread pools 249 Using the threading and queue modules 250 Designing concurrent processing 250 Summary 252 Evaluating conditional expressions Exploiting non-strict dictionary rules Filtering true conditional expressions [v] 254 255 256 Table of Contents Using the operator module instead of lambdas 256 Getting named attributes when using higher-order functions 257 Starmapping with operators 258 Reducing with operators 260 Summary 261 Chapter 14: The PyMonad Library 263 Chapter 15: A Functional Approach to Web Services 281 Downloading and installing 263 Functional composition and currying 264 Using curried higher-order functions 266 Currying the hard way 268 Functional composition and the PyMonad multiplication operator 268 Functors and applicative functors 270 Using the lazy List() functor 271 Monad concepts, the bind() function and the Binary Right Shift operator 274 Implementing simulation with monads 275 Additional PyMonad features 279 Summary 280 The HTTP request-response model 282 Injecting a state via cookies 284 Considering a server with a functional design 284 Looking more deeply into the functional view 285 Nesting the services 286 The WSGI standard 287 Throwing exceptions during WSGI processing 288 Pragmatic WSGI applications 290 Defining web services as functions 291 Creating the WSGI application 292 Getting raw data 294 Applying a filter 295 Serializing the results 296 Serializing data into the JSON or CSV format 298 Serializing data into XML 299 Serializing data into HTML 300 Tracking usage 301 Summary 303 [ vi ] Table of Contents Chapter 16: Optimizations and Improvements 305 Memoization and caching 305 Specializing memoization 307 Optimizing storage 311 Optimizing accuracy 311 Reducing accuracy based on audience requirements 312 Case study – making a chi-squared decision 312 Filtering and reducing the raw data with a Counter object 314 Reading summarized data 316 Computing probabilities from a Counter object 317 Alternative summary approaches 318 Computing expected values and displaying a contingency table 319 Computing the chi-squared value 321 Computing the chi-squared threshold 322 Computing the partial gamma value 323 Computing the complete gamma value 325 Computing the odds of a distribution being random 327 Summary 329 Index 331 [ vii ] Preface Programming languages sometimes fit neatly into tidy categories like imperative and functional. Imperative languages might further subdivide into those that are procedural and those that include features for object-oriented programming. The Python language, however, contains aspects of all of these three language categories. Though Python is not a purely functional programming language, we can do a great deal of functional programming in Python. Most importantly, we can leverage many design patterns and techniques from other functional languages and apply them to Python programming. These borrowed concepts can lead us to create succinct and elegant programs. Python's generator expressions, in particular, avoid the need to create large in-memory data structures, leading to programs which may execute more quickly because they use fewer resources. We can't easily create purely functional programs in Python. Python lacks a number of features that would be required for this. For example, we don't have unlimited recursion, lazy evaluation of all expressions, and an optimizing compiler. Generally, Python emphasizes strict evaluation rules. This means that statements are executed in order and expressions are evaluated from left to right. While this deviates from functional purity, it allows us to perform manual optimizations when writing in Python. We'll take a hybrid approach to functional programming using Python's functional features when they can add clarity or simplify the code and use ordinary imperative features for optimization. There are several key features of functional programming languages that are available in Python. One of the most important is the idea that functions are first-class objects. In some languages, functions exist only as a source code construct: they don't exist as proper data structures at runtime. In Python, functions can use functions as arguments and return functions as results. Preface Python offers a number of higher-order functions. Functions like map(), filter(), and functools.reduce() are widely used in this role. Less obvious functions like sorted(), min(), and max() are also higher-order functions; they have a default function and, consequently, different syntax from the more common examples. Functional programs often exploit immutable data structures. The emphasis on stateless objects permits flexible optimization. Python offers tuples and namedtuples as complex but immutable objects. We can leverage these structures to adapt some design practices from other functional programming languages. Many functional languages emphasize recursion but exploit Tail-Call Optimization (TCO). Python tends to limit recursion to a relatively small number of stack frames. In many cases, we can think of a recursion as a generator function. We can then simply rewrite it to use a yield from statement, doing the tail-call optimization ourselves. We'll look at the core features of functional programming from a Python point of view. Our objective is to borrow good ideas from functional programming languages, and use these ideas to create expressive and succinct applications in Python. What this book covers Chapter 1, Introducing Functional Programming, introduces some of the techniques that characterize functional programming. We'll identify some of the ways to map these features to Python, and finally, we'll also address some ways that the benefits of functional programming accrue when we use these design patterns to build Python applications. Chapter 2, Introducing Some Functional Features, will delve into six central features of the functional programming paradigm. We'll look at each in some detail to see how they're implemented in Python. We'll also point out some features of functional languages that don't apply well to Python. In particular, many functional languages have complex type-matching rules required to support compilation and optimization. Chapter 3, Functions, Iterators, and Generators, will show how to leverage immutable Python objects and generator expressions, and adapt functional programming concepts to the Python language. We'll look at some of the built-in Python collection and how we can leverage them without departing too far from functional programming concepts. Chapter 4, Working with Collections, shows how we can use a number of built-in Python functions to operate on collections of data. This section will focus on a number of relatively simple functions such as any() and all(), which will reduce a collection of values to a single result. [2] Preface Chapter 5, Higher-order Functions, examines the commonly used higher order functions such as map() and filter(). The chapter also includes a number of other functions that are also higher-order functions, as well as how we can create our own higher-order functions. Chapter 6, Recursions and Reductions, shows how we can design an algorithm using recursion and then optimize it into a high performance for loop. We'll also look at some other reductions that are widely used, including the collections.Counter() function. Chapter 7, Additional Tuple Techniques, shows a number of ways in which we can use immutable tuples and namedtuples instead of stateful objects. Immutable objects have a much simpler interface: we never have to worry about abusing an attribute and setting an object into some inconsistent or invalid state. Chapter 8, The Itertools Module, examines a number of functions in the standard library module. This collection of functions simplifies writing programs that deal with collections or generator functions. Chapter 9, More Itertools Techniques, covers the combinatoric functions in the itertools module. These functions are somewhat less useful. This chapter includes some examples that illustrate ill-considered uses of these functions and the consequences of combinatoric explosion. Chapter 10, The Functools Module, will show how to use some of the functions in this module for functional programming. A few of the functions in this module are more appropriate for building decorators, and are left for the next chapter. The other functions, however, provide several more ways to design and implement function programs. Chapter 11, Decorator Design Techniques, shows how we can look at a decorator as a way to build a composite function. While there is considerable flexibility here, there are also some conceptual limitations: we'll look at ways in which overly complex decorators can become confusing rather than helpful. Chapter 12, The Multiprocessing and Threading Modules, points out an important consequence of good functional design: we can distribute the processing workload. Using immutable objects means that we can't corrupt an object because of poorly synchronized write operations. Chapter 13, Conditional Expressions and the Operator Module, will show some ways in which we can break out of Python's strict order of evaluation. There are limitations to what we can achieve here. We'll also look at the operator module and how the operator module can lead to some slight clarification of some simple kinds of processing. [3]