Functional Programming in Java

Why Functional Programming?

Functional programs contain no assignment statements, so variables, once given a value,

never change. More generally, functional programs contain no side-effects at all. A function

call can have no effect other than to compute its result. This eliminates a major source of bugs,

and also makes the order of execution irrelevant—since no side-effect can change an expres￾sion’s value, it can be evaluated at any time. This relieves the programmer of the burden of pre￾scribing the flow of control. Since expressions can be evaluated at any time, one can freely

replace variables by their values and vice versa—that is, programs are “referentially transpar￾ent.” This freedom helps make functional programs more tractable mathematically than their

conventional counterparts.

—John Hughes

“Why Functional Programming Matters”

I call it my billion-dollar mistake … My goal was to ensure that all use of references should be

absolutely safe, with checking performed automatically by the compiler. But I couldn’t resist the

temptation to put in a null reference, simply because it was so easy to implement. This has led

to innumerable errors, vulnerabilities, and system crashes, which have probably caused a bil￾lion dollars of pain and damage in the last forty years.

—Tony Hoare

Program testing can be a very effective way to show the presence of bugs, but is hopelessly inad￾equate for showing their absence.

—Edsger W. Dijkstra

Testing by itself does not improve software quality. Test results are an indicator of quality, but

in and of themselves, they don’t improve it. Trying to improve software quality by increasing

the amount of testing is like trying to lose weight by weighing yourself more often.

—Steve McConnell

The proper use of comments is to compensate for our failure to express ourselves in code.

—Robert C. Martin

In programming the hard part isn’t solving problems, but deciding what problems to solve.

—Paul Graham

Object oriented programming makes code understandable by encapsulating moving parts.

Functional programming makes code understandable by minimizing moving parts.

—Michael Feathers

Licensed to <null>

Functional Programming

in Java

HOW FUNCTIONAL TECHNIQUES

IMPROVE YOUR JAVA PROGRAMS

PIERRE-YVES SAUMONT

MANNING

SHELTER ISLAND

Licensed to <null>

For online information and ordering of this and other Manning books, please visit

www.manning.com. The publisher offers discounts on this book when ordered in quantity.

For more information, please contact

Special Sales Department

Manning Publications Co.

20 Baldwin Road

PO Box 761

Shelter Island, NY 11964

Email: [email protected]

©2017 by Manning Publications Co. All rights reserved.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in

any form or by means electronic, mechanical, photocopying, or otherwise, without prior written

permission of the publisher.

Many of the designations used by manufacturers and sellers to distinguish their products are

claimed as trademarks. Where those designations appear in the book, and Manning

Publications was aware of a trademark claim, the designations have been printed in initial caps

or all caps.

Recognizing the importance of preserving what has been written, it is Manning’s policy to have

the books we publish printed on acid-free paper, and we exert our best efforts to that end.

Recognizing also our responsibility to conserve the resources of our planet, Manning books

are printed on paper that is at least 15 percent recycled and processed without the use of

elemental chlorine.

Manning Publications Co. Development editor: Marina Michaels

20 Baldwin Road Technical development editor: Mark Elston

PO Box 761 Project editor: Janet Vail

Shelter Island, NY 11964 Copyeditor: Andy Carroll

Proofreaders: Katie Tennant and Melody Dolab

Technical proofreader: Alessandro Campeis

Typesetter: Dottie Marsico

Cover designer: Leslie Haimes

ISBN 9781617292736

Printed in the United States of America

1 2 3 4 5 6 7 8 9 10 – EBM – 22 21 20 19 18 17

Licensed to <null>

iii

brief contents

1 ■ What is functional programming? 1

2 ■ Using functions in Java 16

3 ■ Making Java more functional 57

4 ■ Recursion, corecursion, and memoization 94

5 ■ Data handling with lists 124

6 ■ Dealing with optional data 151

7 ■ Handling errors and exceptions 176

8 ■ Advanced list handling 203

9 ■ Working with laziness 230

10 ■ More data handling with trees 256

11 ■ Solving real problems with advanced trees 290

12 ■ Handling state mutation in a functional way 321

13 ■ Functional input/output 342

14 ■ Sharing mutable state with actors 370

15 ■ Solving common problems functionally 394

Licensed to <null>

Licensed to <null>

v

contents

preface xiii

acknowledgments xvi

about this book xvii

1 What is functional programming? 1

1.1 What is functional programming? 2

1.2 Writing useful programs with no side effects 4

1.3 How referential transparency makes programs safer 6

1.4 The benefits of functional programming 7

1.5 Using the substitution model to reason about

programs 8

1.6 Applying functional principles to a simple example 9

1.7 Pushing abstraction to the limit 14

1.8 Summary 15

2 Using functions in Java 16

2.1 What is a function? 17

Functions in the real world 17

2.2 Functions in Java 22

Functional methods 23 ■ Java functional interfaces and

anonymous classes 28 ■ Composing functions 29

Polymorphic functions 29 ■ Simplifying the code by using

lambdas 31

Licensed to <null>

vi CONTENTS

2.3 Advanced function features 33

What about functions of several arguments? 33 ■ Applying

curried functions 34 ■ Higher-order functions 35

Polymorphic higher-order functions 36 ■ Using anonymous

functions 39 ■ Local functions 41 ■ Closures 42

Partial function application and automatic currying 44

Switching arguments of partially applied functions 48

Recursive functions 49 ■ The identity function 51

2.4 Java 8 functional interfaces 52

2.5 Debugging with lambdas 53

2.6 Summary 56

3 Making Java more functional 57

3.1 Making standard control structures functional 58

3.2 Abstracting control structures 59

Cleaning up the code 63 ■ An alternative to if … else 66

3.3 Abstracting iteration 71

Abstracting an operation on lists with mapping 72

Creating lists 73 ■ Using head and tail operations 74

Functionally appending to a list 75 ■ Reducing and folding

lists 75 ■ Composing mappings and mapping compositions 82

Applying effects to lists 82 ■ Approaching functional output 83

Building corecursive lists 84

3.4 Using the right types 87

Problems with standard types 87 ■ Defining value types 90

The future of value types in Java 93

3.5 Summary 93

4 Recursion, corecursion, and memoization 94

4.1 Understanding corecursion and recursion 95

Exploring corecursive and recursive addition examples 95

Implementing recursion in Java 96 ■ Using tail call

elimination 96 ■ Using tail recursive methods and

functions 97 ■ Abstracting recursion 97 ■ Using a drop-in

replacement for stack-based recursive methods 101

4.2 Working with recursive functions 103

Using locally defined functions 104 ■ Making functions tail

recursive 104 ■ Doubly recursive functions: the Fibonacci

example 105 ■ Making the list methods stack-safe and

recursive 108

Licensed to <null>

CONTENTS vii

4.3 Composing a huge number of functions 111

4.4 Using memoization 114

Memoization in imperative programming 114 ■ Memoization

in recursive functions 115 ■ Automatic memoization 117

4.5 Summary 123

5 Data handling with lists 124

5.1 How to classify data collections 125

Different types of lists 125 ■ Relative expected list

performance 126 ■ Trading time against memory space,

and time against complexity 127 ■ In-place mutation 128

Persistent data structures 129

5.2 An immutable, persistent, singly linked list

implementation 130

5.3 Data sharing in list operations 133

More list operations 135

5.4 Using recursion to fold lists with higher-order

functions 140

Heap-based recursive version of foldRight 146 ■ Mapping and

filtering lists 148

5.5 Summary 150

6 Dealing with optional data 151

6.1 Problems with the null pointer 152

6.2 Alternatives to null references 153

6.3 The Option data type 156

Getting a value from an Option 158 ■ Applying functions to

optional values 160 ■ Dealing with Option composition 161

Option use cases 163 ■ Other ways to combine options 167

Composing List with Option 169

6.4 Miscellaneous utilities for Option 171

Testing for Some or None 171 ■ equals and hashcode 172

6.5 How and when to use Option 172

6.6 Summary 175

7 Handling errors and exceptions 176

7.1 The problems to be solved 177

Licensed to <null>

viii CONTENTS

7.2 The Either type 178

Composing Either 179

7.3 The Result type 181

Adding methods to the Result class 183

7.4 Result patterns 184

7.5 Advanced Result handling 191

Applying predicates 191 ■ Mapping failures 192 ■ Adding

factory methods 195 ■ Applying effects 196 ■ Advanced result

composition 199

7.6 Summary 202

8 Advanced list handling 203

8.1 The problem with length 204

The performance problem 204 ■ The benefit of memoization 205

The drawbacks of memoization 205 ■ Actual performance 207

8.2 Composing List and Result 207

Methods on List returning Result 208 ■ Converting from

List<Result> to Result<List> 209

8.3 Abstracting common List use cases 212

Zipping and unzipping lists 212 ■ Accessing elements by

their index 215 ■ Splitting lists 217 ■ Searching for

sublists 221 ■ Miscellaneous functions for working with

lists 222

8.4 Automatic parallel processing of lists 225

Not all computations can be parallelized 226 ■ Breaking

the list into sublists 226 ■ Processing sublists in parallel 227

8.5 Summary 229

9 Working with laziness 230

9.1 Understanding strictness and laziness 230

Java is a strict language 231 ■ The problem with strictness 232

9.2 Implementing laziness 233

9.3 Things you can’t do without laziness 234

9.4 Why not use the Java 8 Stream? 235

9.5 Creating a lazy list data structure 236

Memoizing evaluated values 237 ■ Manipulating streams 241

Licensed to <null>

CONTENTS ix

9.6 The true essence of laziness 243

Folding streams 245

9.7 Handling infinite streams 251

9.8 Avoiding null references and mutable fields 253

9.9 Summary 255

10 More data handling with trees 256

10.1 The binary tree 257

Balanced and unbalanced trees 258 ■ Size, height, and

depth 258 ■ Leafy trees 259 ■ Ordered binary trees or

binary search trees (BST) 259 ■ Insertion order 260

Tree traversal order 261

10.2 Implementing the binary search tree 263

10.3 Removing elements from trees 268

10.4 Merging arbitrary trees 270

10.5 Folding trees 275

Folding with two functions 276 ■ Folding with a single

function 279 ■ Which fold implementation to choose 279

10.6 Mapping trees 281

10.7 Balancing trees 282

Rotating trees 282

Balancing trees using the Day-Stout-Warren algorithm 285

Automatically balancing trees 287 ■ Solving the right

problem 288

10.8 Summary 288

11 Solving real problems with advanced trees 290

11.1 Better performance and stack safety

with self-balancing trees 291

The basic tree structure 291 ■ Inserting an element into the

red-black tree 295

11.2 A use case for the red-black tree: maps 300

Implementing Map 301 ■ Extending maps 303

Using Map with noncomparable keys 304

11.3 Implementing a functional priority queue 307

The priority queue access protocol 307 ■ Priority queue use

cases 307 ■ Implementation requirements 308 ■ The leftist

Licensed to <null>

x CONTENTS

heap data structure 308 ■ Implementing the leftist heap 309

Implementing the queue-like interface 313

11.4 A priority queue for noncomparable elements 314

11.5 Summary 319

12 Handling state mutation in a functional way 321

12.1 A functional random number generator 322

The random number generator interface 323

Implementing the random number generator 324

12.2 A generic API for handling state 327

Working with state operations 328 ■ Composing state

operations 329 ■ Recursive state operations 331

12.3 Generic state handling 333

State patterns 334 ■ Building a state machine 335

When to use state and the state machine 340

12.4 Summary 341

13 Functional input/output 342

13.1 Applying effects in context 343

What are effects? 343 ■ Implementing effects 344

More-powerful effects for failures 346

13.2 Reading data 349

Reading data from the console 349 ■ Reading from

a file 354 ■ Testing with input 355

13.3 Really functional input/output 356

How can input/output be made fully functional? 356

Implementing purely functional input/output 357

Combining IO 358 ■ Handling input with IO 359

Extending the IO type 361 ■ Making the IO type

stack-safe 364

13.4 Summary 369

14 Sharing mutable state with actors 370

14.1 The actor model 371

Asynchronous messaging 372 ■ Handling parallelization 372

Handling actor state mutation 372

Licensed to <null>

CONTENTS xi

14.2 Building the actor framework 373

Limitations of this actor framework 374 ■ Designing the actor

framework interfaces 374 ■ The AbstractActor

implementation 376

14.3 Putting actors to work 377

Implementing the ping-pong example 378 ■ A more serious

example: running a computation in parallel 379 ■ Reordering the

results 385 ■ Fixing the performance problem 388

14.4 Summary 393

15 Solving common problems functionally 394

15.1 Using assertions to validate data 395

15.2 Reading properties from file 399

Loading the property file 400 ■ Reading properties as

strings 400 ■ Producing better error messages 402

Reading properties as lists 405 ■ Reading enum

values 406 ■ Reading properties of arbitrary types 407

15.3 Converting an imperative program: the XML reader 409

Listing the necessary functions 411 ■ Composing the functions

and applying an effect 412 ■ Implementing the functions 412

Making the program even more functional 414 ■ Fixing the

argument type problem 417 ■ Making the element-processing

function a parameter 418 ■ Handling errors on element

names 420

15.4 Summary 421

appendix A Using Java 8 functional features 422

appendix B Monads 429

appendix C Where to go from here 434

index 440

Licensed to <null>

Licensed to <null>

xiii

preface

Writing programs is fun and rewarding. Programming is an activity that many people

would do for fun, and yet are paid for. In this sense, a programmer is a bit like an

actor, a musician, or a professional football player. It seems like a dream until you, as a

programmer, begin to have real responsibilities. Writing games or office applications

isn’t really a big deal from this point of view. If your application has a bug, you simply

fix it and release a new version. But if you write applications that people depend on,

and if you can’t simply release a new version and have your users install it themselves,

it’s another story. Of course, Java isn’t meant for writing applications for monitoring

nuclear plants or flying airplanes, or any system in which a simple bug could put

human life at risk. But if your application is used to manage internet backbones, you

wouldn’t like a nasty bug to be discovered one day before the Olympic Games open,

causing a TV transmission failure for a whole country. For such applications, you want

to be sure that your program can be proven correct.

Most imperative programs can’t be proven correct. Tests only allow us to prove

programs incorrect when they fail. Successful tests don’t prove much. What you

release are programs that you weren’t able to prove incorrect. With single-threaded

programs, extensive tests may let you show that your code is mostly correct. But with

multithreaded applications, the number of possible condition combinations makes

that impossible. Clearly, we need a different way to write programs. Ideally, it would be

a way that allows us to prove that a program is correct. Because this is generally not

fully possible, a good compromise is a clear separation between parts of the program

that can be proven correct and parts that can’t. This is what functional programming

techniques offer.

Licensed to <null>