Foreword

Creative Scala is aimed at developers who have no prior experience in Scala. It is designed to give you a fun introduction to functional programming. We assume you have some very basic familiarity with another programming language but little or no experience with Scala or other functional languages.

We have three goals with this book:

1. To give an introduction to functional programming so that you can calculate and reason about programs, and pick up and understand other introductory books on functional programming.

2. To teach you enough Scala that you can explore your own interests in and using Scala.

3. To present all this in a fun, gentle, and interesting way via two-dimensional computer graphics.

Our motivation comes from our own experience learning programming, studying functional programming, and teaching Scala to commercial developers.

Firstly, we believe that functional programming is the future. Since we’re assuming you have little programming experience we won’t go into the details of the differences between functional programming and object-oriented programming that you may have already experienced. Suffice to say there are different ways to think about and write computer programs, and we’ve chosen the functional programming approach.

The reason for choosing functional programming are more interesting. It’s common to teach programming by what we call the “bag of syntax” approach. In this approach a programming language is taught a collection of syntactical features (variables, for loops, while loops, methods) and students are left to figure out on their own when to use each feature. We’ve seen this method fail both when we were undergraduates learning programming, and as postgraduates teaching programming, as students simply have no systematic way to break down a problem and turn it into code. The result is that many students dropped out due to the poor quality of teaching. The students that remained tended to, like us, already have extensive programming experience.

Let’s think back to primary school maths, specifically column addition. This is the basic way we’re taught to add up numbers when they’re too big to do in our head. So, for example, adding up 266 + 385, we would line up the columns, carry the tens and so on. Now maybe maths wasn’t your favorite subject but there are some important lessons here. The first is that we’re given a systematic way to arrive at the solution. We can calculate the solution once we realise this is a problem that requires column addition. The second point is that we don’t even have to understand why column addition works (though it helps) to use it. So long as we follow the steps we’ll get the correct answer.

The remarkable thing about functional programming is that it works like column addition. We have recipes that are guaranteed to give us the correct answer if we follow them correctly. We call this calculating a program. This is not to say that programming is without creativity, but the challenge is to understand the structure of the problem and once we’ve done that the recipe we should use follows immediately. The code itself is not the interesting part.

We’re teaching functional programming using Scala, but not Scala itself. Scala is a language that is in demand right now. Scala programmers can relatively easily get jobs in a variety of industries, and this is an important motivation for learning Scala. One of the reasons for Scala’s popularity is that is straddles object-oriented programming, the old way of programming, and functional programming. There is a lot of code written in an object-oriented style, and a lot of programmers who are used to that style. Scala gives a gentle way from object-oriented programming to functional programming. However this means Scala is a large language, and the interaction between the object-oriented and functional parts can be confusing. We believe that functional programming is much more effective than object-oriented programming, and for new programmers there is no need to add the confusion of learning object-oriented techniques at the same time. That can come later. Therefore this book is exclusively using the functional programming parts of Scala.

Finally, we’ve chosen what we hope is a fun method to explore functional programming and Scala: computer graphics. There are many introductions to Scala, but the majority use examples that either relate to business or mathematics. For example, one of the first exercises in the very popular Coursera course is to implement sets via indicator functions. We feel if you’re the type of person who likes directly working with these sort of concepts you already have plenty of content available. We want to target a different group: people who perhaps thought that maths was not for them but nonetheless have an interest or appreciation in the visual arts. We won’t lie: there is maths in this book, but we hope we manage to motivate and indeed visualise the concepts in a way that makes them less intimidating.

Although this book will give you the basic mental model required to become competent with Scala, you won’t finish knowing everything you need to be self-sufficient. For further advancement we recommend considering one of the many excellent Scala textbooks out there, including our own Essential Scala.

If you are working through the exercises on your own, we highly recommend joining our Gitter chat room to provide get help with the exercises and provide feedback on the book.

The text of Creative Scala is open source, as is the source code for the Doodle drawing library used in the exercises. You can grab the code from our GitHub account. Contact us on Gitter or by email if you would like to contribute.

Thanks for downloading and happy creative programming!

—Dave and Noel

Notes on the Early Access Edition

Acknowledgements

Creative Scala was written by Dave Gurnell and Noel Welsh. Many thanks to Richard Dallaway, Jonathan Ferguson, and the team at Underscore for their invaluable contributions and extensive proof reading.

Thanks also to the many people who pointed out errors or made suggestions to improve the book: Neil Moore; Kelley Robinson, Julie Pitt, and the other ScalaBridge organizers; d43; Matt Kohl; Alexa Kovachevich and all the other students who worked through Creative Scala at ScalaBridge, at another event, or on their own; and the many awesome members of the Scala community who gave us comments and suggestions in person. Finally, we have large amount of gratitude for Bridgewater, and particularly Lauren Cipicchio, who perhaps unknowingly funded a good portion of the initial development of the second version of the Creative Scala, and provided the first few rounds of students.

Finally, Creative Scala owes a large intellectual debt to the work of many researchers working in programming language theory and Computer Science education. In particular we’d like to highlight:

• the work of the PLT research group, and in particular the book “How to Design Programs”, by Matthew Flatt, Matthias Felleisen, Robert Bruce Findler, and Shriram Krishnamurthi; and
• the “creative coding” approach to introductory programming pioneered by Mark Guzdial, Dianna Xu, and others.

1 Getting Started

Our first step is to install the software we need to work with Creative Scala. We describe two pathways here:

1. Working with a text editor and a terminal. We recommend this setup to people completely new to programming as there are fewer moving parts.
2. Working with IntelliJ IDEA. We recommend this setup to people who are used to using an IDE or are uncomfortable with the terminal.

If you’re an experienced developer with a setup you are happy with just keep the tools you know and adapt the instructions below as needed.

If all this stuff is new to you, the rest of the chapter has some background.

1.1 Installing Terminal Software and a Text Editors

This section is our recommended setup for people new to programming, and describes how to setup Creative Scala with the terminal and a text editor. We need to install:

• the JVM;
• Git;
• a text editor; and
• the template project for Creative Scala.

1.1.1 OS X

Open the terminal. (Click the magnifying glass icon on the top righthand side of the toolbar. Type in “terminal”.)

Install Java. Type into the terminal

java

If this runs you already have Java installed. Otherwise it will prompt you to install Java.

Install homebrew. Paste into the terminal

/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

Install git using homebrew. At the terminal, type

brew install git

Now install the text editor Atom. Again type at the terminal

brew install Caskroom/cask/atom

Install Scala support inside Atom: Settings > Install > language-scala

Now we will use Git to get an SBT project that will work with Creative Scala. Type

git clone https://github.com/underscoreio/creative-scala-template.git

Now change to the directory we just created and run SBT.

cd creative-scala-template
./sbt.sh

SBT should start. Within SBT type console. Finally type

Example.image.draw()

and an image of three circles should appear!

If you’ve made it this far you’ve successfully installed all the software you need for work through Creative Scala.

The final step is to load Atom and use it to open Example.scala, which you can find in src/main/scala.

1.1.2 Windows

Download and install Java. Search for the “JDK” (Java development kit). This will take you to Oracle’s site. Accept their license and download the JDK. Run the installer you just downloaded.

Download and install Atom. Go to https://atom.io/ and download Atom for Windows. Run the installer you’ve just downloaded.

Download and install Git. Go to https://git-scm.com/ and download Git for Windows. Run the installer you’ve just downloaded. At the very end it gives you the option to open Git. Select that option. A window will open up with a command prompt. Type

git clone https://github.com/underscoreio/creative-scala-template.git

Open a normal command-prompt. Click on the Windows icon on the bottom left of the screen. In the search box enter “cmd” and run the program it finds. In the window that is opened up type

cd creative-scala-template

which will change into the directory of the Creative Scala template project we just downloaded. Type

sbt.bat

to start SBT. Within SBT type console. Finally type

Example.image.draw()

and an image of three circles should appear!

If you’ve made it this far you’ve successfully installed all the software you need for work through Creative Scala.

The final step is to load Atom and use it to open Example.scala, which you can find in the directory src\main\scala.

1.1.3 Linux

Follow the OS X instructions, using your distributions package manager to install software in place of Homebrew.

1.2 IntelliJ

IntelliJ is an integrated development environment (IDE) for Scala and other programming languages. It integrates an number of programming tools into one application, and we recommend it for people who are used to using other IDEs such as Visual Studiol or Eclipse.

Start by downloading and installing IntelliJ. You can use the free community edition for Creative Scala. When installing IntelliJ you will be asked a lot of questions. You can accept the defaults for the most part. When you are asked about “featured plugins”, make sure you install the Scala plug-in.

Once you have completed the configuration you will be presented with a dialog asking if you want to create a new project, import a project, open a file, or check out from version control. Choose “checkout from version control”, and select GitHub.

In the dialog box that opens change “Auth type” to Token. Now visit GitHub in a web browser. Select your account (top right hand of the page). Choose “Settings” and then choose “Personal access tokens”. Generate a token. Call it “intellij” and select the “repo” check box. Copy the long string of numbers and text and paste it into the “Token” box. Now login to GitHub.

Install the SBT console add-on.

1.3 Background

This section gives some background information on some of the tools we’ll be using. If you’re an experienced developer a lot of this will be old hat, and you can skip it. If you’re not, this will hopefully give some useful context to the software we’ll be working with.

1.3.1 The Terminal

Back when the world was young and computing was in its infancy, the common user interface of graphical windows, a cursor controlled by a mouse, and interaction by direct manipulation didn’t exist. Instead users typed in commands at a device called a terminal. The direct manipulation interface is superior for most uses, but there are some cases for which the terminal or command line is preferable. For example, if we wanted to work out how much space was used by all the files which names starting with data in Linux or OS X we can execute the command

du -hs data*

We can break this down into three components:

• the command du means disk usage;
• the flags -hs mean to print a human readable summary; and
• the pattern data* means all the files whose names begin with data.

Doing this with a direct manipulation interface would be much more time consuming.

The command line has a steep learning curve, but the reward is an extremely powerful tool. Our usage of the terminal will be very limited, so don’t worry if you find the example above intimidating!

1.3.2 Text Editors

You’re probably used to writing documents in a word processor. A word processor allows us to write text and control the formatting of how it appears on the (increasingly rare) printed page. A word processor includes powerful commands, such as a spell checker and automatic table of contents generation, to make editing prose easier.

A text editor is like a word processor for code. Whereas a word processor is concerned about visual presentation of text, a text editor has many programming specific functions. Typical examples include powerful tools to search and replace text, and the ability to quickly jump between the many different files that make up a project.

Text editors date back to the days of terminals and perhaps surprisingly some of these tools are still in use. The two main ancient and glorious text editors that survive are called Emacs and Vim. They have very different approaches (except when they don’t) and developers tend to use one or the other. I’ve been using Emacs for about twenty years, and thus I know in my bones that Emacs is the greatest of all possible text editors and Vim users are knuckle-draggers lumbered with poor taste and an inferior tool. Vim users no doubt think the same about me.

If there is one thing that unites Vim and Emacs users it’s the sure knowledge that new-fangled text editors like Sublime Text and Atom are bringing about the downfall of our civilization. Nonetheless we recommend using Atom if you’re new to this text editing game. Both Vim and Emacs were created before the common interfaces in use today were created, and using them requires learning a very different way of working.

1.3.3 The Compiler

The code we write in a text editor is not in a form that a computer can run. A compiler translates it into something the computer can run. As it does this it performs certain checks on the code. If these checks don’t pass the code won’t be compiled and the compiler will print an error message instead. We’ll learn more about what the compiler can check and what it can’t in the rest of this book.

When we said the compiler translates the code is something the computer can run, this is not the complete truth in the case of Scala. The output of the compiler is something called bytecode, and another program, called the Java Virtual Machine (JVM), runs this code¹.

1.3.4 Integrated Development Environments

Integrated development environments (IDEs) are an alternative approach that combine a text editor, a compiler, and several other programmer tools into a single program. Some people swear by IDEs, while some people prefer to use the terminal and a text editor. Our recommendation if you’re new to programming is to take the terminal-and-text-editor approach. If you’re already used to an IDE then IntelliJ IDEA is currently the best IDE for Scala development.

1.3.5 Version Control

Version control is the final tool we’ll use. A version control system is a program that allows us to keep a record of all the changes that have been made to a group of files. It’s very useful for allowing multiple people to work on a project at the same time, and it ensures people don’t accidentally overwrite each others changes. This is not a huge concern in Creative Scala, but it is good to get some exposure to version control now.

The version control software we’ll use is called Git. It’s powerful but complex. The good news is we don’t need to learn much about Git. Most of our use of Git will be via a website called GitHub, which allows people to share software that is stored in Git. We use GitHub to share the software used in Creative Scala.

1.3.6 Onward!

Now that we’ve got some background, let’s move on to installing the software we need to write Scala code.

1.4 GitHub

We have created a template for you that will get you set up with all the code you need to work through Creative Scala. This template is stored on GitHub, a website for sharing code.

You can copy the template onto your computer, which Git calls cloning, but this means you won’t be able to save any changes you make back to GitHub where other people can view them.

If you want to be able to share your changes, you need to make a copy of the template project on GitHub that you own. Git calls this forking. You fork the repository on GitHub and then clone your fork to your computer. Then you can save your changes back to your fork on GitHub.

To start this process you need to create a GitHub account, if you do not have one already.

Once you have an account, visit the template project in your browser. At the top right is button called “Fork”. Press this button to create your own copy of the template. You will be taken to a web page displaying your own fork of the template. Remember the name of this repository. It should be something like yourname/creative-scala-template where yourname is your GitHub user name.

Now cloning your fork is as simple as running this command and replacing yourname with your actual GitHub user name.

git clone git@github.com:yourname/creative-scala-template.git

Now any changes you make can be sent back to your fork on GitHub. The process for doing this in Git is a bit involved. When you’ve made a change you must:

• add the change to what’s called Git’s index;
• commit the change; and finally
• push the change to the fork.

Here’s an example of using the command line to do this.

git add
git commit -m "Explain here what you did"
git push

GitHub makes a nice free graphical tool for using Git, called GitHub Desktop. It’s probably the easiest way to use Git when you’re getting started.

2 Expressions, Values, and Types

Scala programs have three fundamental building blocks: expressions, values, and types. In this section, we explore these concepts.

Here’s a very simple expression:

1 + 2

An expression is a fragment of Scala code. We can write expressions in a text editor, or on a piece of paper, or on a wall; expressions are like writing. Just like writing must be read for it to have any effect on the world (and the reader has to understand the language the writing is written in), the computer must run an expression for it to have an effect. The result of running an expression is a value. Values live in the computer’s memory, in the same way that the result of reading some writing lives in the reader’s head. We will also say expressions are evaluated or executed to describe the process of transforming them into values.

We can evaluate expressions immediately by writing them at the console and pressing “Enter” (or “Return”). Try it now.

1 + 2
// res1: Int = 3

The console responds with the value the expression evaluates to, and the type of the expression.

The expression 1 + 2 evaluates to the value 3. We can write down the number three here on the page, but the real value is something stored in the computer’s memory. In this case, it is a 32-bit integer represented in two’s-complement. The meaning of “32-bit integer represented in two’s-complement” is not important. We just mention it to emphasize the fact the computer’s representation of the value 3 is the true value, not the numeral written here or displayed by the console.

Types are the final piece of the puzzle. A type describes a set of values. The expression 1 + 2 has the type Int, which means the value the expression evaluates to will be one of the over four billion values the computer understands to be integers. We determine the type of an expression without running it, which is why the type Int doesn’t tell us which specific value the expression evalutes to.

Before a Scala program is run, it must be compiled. Compilation checks that a program makes sense. It must be syntactically correct, meaning it must be written according to the rules of Scala. For example (1 + 2) is syntactically correct, but (1 + 2 is not because there is no ) to match the (. It must also type check, meaning the types must be correct for the operations we’re trying to do. 1 + 2 type checks (we are adding integers), but 1.toUpperCase does not (there is no concept of upper and lower case for integers.)

Only programs that successfully compile can be run. We can think of compilation as being analogous to the rules of grammar in writing. The sentence “FaRf fjrmn;l df.fd” is syntactically incorrect in English. The arrangement of letters doesn’t form any words. The sentence “dog fly a here no” is made out of valid words but their arrangement breaks the rules of grammar—analogous to the type checks that Scala performs.

It is important to remember that type checking is done before a program runs. If you have used a language like Python or Javascript, which are sometimes called “dynamically typed”, there is no type checking done before a program runs. In a “statically typed” language like Scala the type checking catches some potential errors for us before we run the code. What is sometimes called a type in a dynamically typed language is not a type as we understand it. Types, for us, exist at at the time when a program is compiled, which we will call compile time. At time when a program runs, which we call run time, we have only values. Values may record some information about the type of the expression that created them. If they do we call these tags, or sometimes boxes. Not all values are tagged or boxed. Avoiding tagging, which is also called type erasure, allows for more efficient programs.

2.1 Literal Expressions

We’ll now start to explore the various forms of expressions in Scala, starting with the simplest expressions, literals. Here’s a literal expression:

3
// res0: Int = 3

A literal evaluates to “itself.” How we write the expression and how the console prints the value are the same. Remember though, there is a difference between the written representation of a value and its actual representation in the computer’s memory.

Scala has many different forms of literals. We’ve already seen Int literals. There is a different type, and a different literal syntax, for what are called floating point numbers. This corresponds to a computer’s approximation of the real numbers. Here’s an example:

0.1
// res1: Double = 0.1

As you can see, the type is called Double.

Numbers are well and good, but what about text? Scala’s String type represents a sequence of characters. We write literal strings by putting their contents in double quotes.

"To be fond of dancing was a certain step towards falling in love."
// res2: String = "To be fond of dancing was a certain step towards falling in love."

Sometimes we want to write strings that span several lines. We can do this by using triple double quotes, as below.

"""
A new, a vast, and a powerful language is developed for the future use of analysis,
in which to wield its truths so that these may become of more speedy and accurate
practical application for the purposes of mankind than the means hitherto in our
possession have rendered possible.

  -- Ada Lovelace, the world's first programmer
"""
// res3: String = """
// A new, a vast, and a powerful language is developed for the future use of analysis,
// in which to wield its truths so that these may become of more speedy and accurate
// practical application for the purposes of mankind than the means hitherto in our
// possession have rendered possible.
// 
//   -- Ada Lovelace, the world's first programmer
// """

A String is a sequence of characters. Characters themselves have a type, Char, and character literals are written in single quotes.

'a'
// res4: Char = 'a'

Finally we’ll look at the literal representations of the Boolean type, named after English logician George Boole. This fancy name just means a value that can be either true or false, and this indeed is how we write boolean literals.

true
// res5: Boolean = true
false
// res6: Boolean = false

With literal expressions, we can create values, but we won’t get very far if we can’t somehow manipulate the values we’ve created. We’ve seen a few examples of more complex expressions like 1 + 2. In the next section, we’ll learn about objects and methods, which will allow us to understand how this, and more interesting expressions, work.

2.2 Values are Objects

In Scala all values are objects. An object is a grouping of data and operations on that data. For example, 2 is an object. The data is the integer 2, and the operations on that data are familiar operations like +, -, and so on. We call operations of an object the object’s methods.

2.2.1 Method Calls

We interact with objects by calling or invoking methods. For example, we can get the uppercase version of a String by calling its toUpperCase method.

"Titan!".toUpperCase
// res0: String = "TITAN!"

Some methods accept parameters or arguments, which control how the method works. The take method, for example, takes characters from a String. We must pass a parameter to take to specify how many characters we want.

"Gilgamesh went abroad in the world".take(3)
// res1: String = "Gil"
"Gilgamesh went abroad in the world".take(9)
// res2: String = "Gilgamesh"

A method call is an expression, and thus evaluates to an object. This means we can chain method calls together to make more complex programs:

"Titan!".toUpperCase.toLowerCase
// res3: String = "titan!"

anExpression.methodName(param1, ...)

anExpression.methodName

2.2.2 Operators

We have said that all values are objects, and we call methods with the syntax object.methodName(parameter). How then do we explain expressions like 1 + 2?

In Scala, and expression written a.b(c) can be written a b c. So these are equivalent:

1 + 2
// res4: Int = 3
1.+(2)
// res5: Int = 3

This first way of calling a method is known an operator style.

2.3 Types

Now that we can write more complex expressions, we can talk a little more about types.

One use of types is stopping us from calling methods that don’t exist. The type of an expression tells the compiler what methods exist on the value it evaluates to. Our code won’t compile if we try to call to a method that doesn’t exist. Here are some simple examples.

"Brontë" / "Austen"
1.take(2)
// error: value / is not a member of String
// "Brontë" / "Austen"
// ^^^^^^^^^^
// error: value take is not a member of Int
// 1.take(2)
// ^^^^^^

It really is the type of the expression that determines what methods we can call, which we can demonstrate by calling methods on the result of more complex expressions.

(1 + 3).take(1)
// error: value take is not a member of Int
// (1 + 3).take(1)
//  ^^^^^^^^^^^

This process of type checking also applies to the parameter of methods.

1.min("zero")
// error: type mismatch;
//  found   : String("zero")
//  required: Int
// 1.min("zero")
//       ^^^^^^

Types are a property of expressions and thus exist at compile time (as we have discussed before.) This means we can determine the type of an expression even if evaluating it results in an error at run time. For example, dividing an Int by zero causes a run-time error.

1 / 0
// java.lang.ArithmeticException: / by zero
//  at repl.Session$App$$anonfun$4.apply$mcI$sp(types.md:27)
//  at repl.Session$App$$anonfun$4.apply(types.md:27)
//  at repl.Session$App$$anonfun$4.apply(types.md:27)

The expression 1 / 0 still has a type, and we can get that type from the console as shown below.

:type 1 / 0
// Int

We can also write a compound expression including a sub-expression that will fail at run-time.

(2 + (1 / 0) + 3)
// java.lang.ArithmeticException: / by zero
//  at repl.Session$App$$anonfun$5.apply$mcI$sp(types.md:35)
//  at repl.Session$App$$anonfun$5.apply(types.md:35)
//  at repl.Session$App$$anonfun$5.apply(types.md:35)

This expression also has a type.

:type (2 + (1 / 0) + 3)
// Int

2.4 Exercises

2.4.0.1 Arithmetic

Write an expression using integer literals, addition, and subtraction that evaluates to 42.

1 + 43 - 2
// res0: Int = 42

2.4.0.2 Appending Strings

Join together two strings (known as appending strings) using the ++ method. Write equivalent expressions using both the normal method call style and the operator style.

"It is a truth ".++("universally acknowledged")
// res1: String = "It is a truth universally acknowledged"
"It is a truth " ++ "universally acknowledged"
// res2: String = "It is a truth universally acknowledged"

2.4.0.3 Precedence

In mathematics we learned that some operators take precedence over others. For example, in the expression 1 + 2 * 3 we should do the multiplication before the addition. Do the same rules hold in Scala?

1 + 2 * 3
// res3: Int = 7
1 + (2 * 3)
// res4: Int = 7
(1 + 2) * 3
// res5: Int = 9

2.4.0.4 Types and Values

Which of the following expressions will not compile? Of the expressions that will compile, what is their type? Which expressions fail at run-time?

1 + 2

"3".toInt

"Electric blue".toInt
// java.lang.NumberFormatException: For input string: "Electric blue"
//  at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
//  at java.lang.Integer.parseInt(Integer.java:580)
//  at java.lang.Integer.parseInt(Integer.java:615)
//  at scala.collection.immutable.StringLike.toInt(StringLike.scala:304)
//  at scala.collection.immutable.StringLike.toInt$(StringLike.scala:304)
//  at scala.collection.immutable.StringOps.toInt(StringOps.scala:33)
//  at repl.Session$App$$anonfun$9.apply$mcI$sp(exercises.md:48)
//  at repl.Session$App$$anonfun$9.apply(exercises.md:48)
//  at repl.Session$App$$anonfun$9.apply(exercises.md:48)

"Electric blue".take(1)

"Electric blue".take("blue")

1 + ("Moonage daydream".indexOf("N"))

1 / 1 + ("Moonage daydream".indexOf("N"))

1 / (1 + ("Moonage daydream".indexOf("N")))
// java.lang.ArithmeticException: / by zero
//  at repl.Session$App$$anonfun$14.apply$mcI$sp(exercises.md:80)
//  at repl.Session$App$$anonfun$14.apply(exercises.md:80)
//  at repl.Session$App$$anonfun$14.apply(exercises.md:80)

1 + 2
// res12: Int = 3

"3".toInt
// res13: Int = 3

"Electric blue".toInt
// java.lang.NumberFormatException: For input string: "Electric blue"
//  at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
//  at java.lang.Integer.parseInt(Integer.java:580)
//  at java.lang.Integer.parseInt(Integer.java:615)
//  at scala.collection.immutable.StringLike.toInt(StringLike.scala:304)
//  at scala.collection.immutable.StringLike.toInt$(StringLike.scala:304)
//  at scala.collection.immutable.StringOps.toInt(StringOps.scala:33)
//  at repl.Session$App$$anonfun$17.apply$mcI$sp(exercises.md:100)
//  at repl.Session$App$$anonfun$17.apply(exercises.md:100)
//  at repl.Session$App$$anonfun$17.apply(exercises.md:100)

"Electric blue".take(1)
// res14: String = "E"

"Electric blue".take("blue")
// error: type mismatch;
//  found   : String("blue")
//  required: Int
// "Electric blue".take("blue")
//                      ^^^^^^

1 + ("Moonage daydream".indexOf("N"))
// res16: Int = 0

1 / 1 + ("Moonage daydream".indexOf("N"))
// res17: Int = 0

1 / (1 + ("Moonage daydream".indexOf("N")))
// java.lang.ArithmeticException: / by zero
//  at repl.Session$App$$anonfun$22.apply$mcI$sp(exercises.md:132)
//  at repl.Session$App$$anonfun$22.apply(exercises.md:132)
//  at repl.Session$App$$anonfun$22.apply(exercises.md:132)

2.4.0.5 Floating Point Failings

When we introduced Doubles, I said they are an approximation to the real numbers. Why do you think this is? Think about representing numbers like ⅓ and π. How much space would it take to represent these numbers in decimal?

2.4.0.6 Beyond Expressions

In our current model of computation there are only three components: expressions (program text) with types, that evaluate to values (something within the computer’s memory). Is this sufficient? Could we write a stock market or a computer game with just this model? Can you think of ways to extend this model?

3 Computing With Pictures

So far we have computed using numbers, strings, and other simple objects. From here on out we will focus our attention on computing with pictures, and later with animations. Pictures offer us more immediate creative opportunities, and they make our program output tangible in a way that other methods can’t deliver.

We’ll use a library called Doodle to help us with creating graphics. In this chapter we will learn the basics of Doodle.

import doodle.core._
import doodle.image._
import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

3.1 Images

Let’s start with some simple shapes, programming at the console as we’ve done before.

Image.circle(10)
// res0: Image = Circle(10.0)

What is happening here? Image is an object and circle a method on that object. We pass to circle a parameter, 10 that gives the diameter of the circle we’re constructing. Note the type of the result—an Image.

Image.circle(10)
// res1: Image = Circle(10.0)

We draw the circle by calling the draw method.

Image.circle(10).draw()

A window should appear as shown in fig. 1.

Figure 1: A circle

Doodle supports a handful of “primitive” images: circles, rectangles, and triangles. Let’s try drawing a rectangle.

Image.rectangle(100, 50).draw()

The output is shown in fig. 2.

Figure 2: A rectangle

Finally let’s try a triangle, for which the output is shown in fig. 3.

Image.triangle(60, 40).draw()

Figure 3: A triangle

Exercises

I Go Round in Circles

Create circles that are 1, 10, and 100 units wide. Now draw them!

Image.circle(1)
Image.circle(10)
Image.circle(100)

Image.circle(1).draw()
Image.circle(10).draw()
Image.circle(100).draw()

My Type of Art

What is the type of a circle? A rectangle? A triangle?

:type Image.circle(10)
// doodle.core.Image
:type Image.rectangle(10, 10)
// doodle.core.Image
:type Image.triangle(10, 10)
// doodle.core.Image

Not My Type of Art

What’s the type of drawing an image? What does this mean?

:type Image.circle(10).draw()
// Unit

()

:type ()
// Unit

3.2 Layout

We can seen how to create primitive images. We can combine together images using layouts methods to create more complex images. Try the following code—you should see a circle and a rectangle displayed beside one another, as in fig. 4.

(Image.circle(10).beside(Image.rectangle(10, 20))).draw()

Figure 4: A circle beside a rectangle

Image contains several layout methods for combining images, described in tbl. 1. Try them out now to see what they do.

Exercises

The Width of a Circle

Create the picture fig. 5 using the layout methods and basic images we’ve covered so far.

Figure 5: The width of a circle

(Image
   .circle(20)
   .beside(Image.circle(20))
   .beside(Image.circle(20))).on(Image.circle(60))
// res0: Image = On(
//   Beside(Beside(Circle(20.0), Circle(20.0)), Circle(20.0)),
//   Circle(60.0)
// )

3.3 Color

In addition to layout, Doodle has some simple operators to add a splash of colour to our images. Try these out the methods described in tbl. 2 to see how they work.

Doodle has various ways of creating colours. The simplest are the predefined colours in CommonColors.scala. Some of the most commonly used are described in tbl. 3.

Exercises

Evil Eye

Make the image in fig. 6, designed to look like a traditional amulet protecting against the evil eye. I used cornflowerBlue for the iris, and darkBlue for the outer color, but experiment with your own choices!

Figure 6: No evil eyes here!

Image
  .circle(10)
  .fillColor(Color.black)
  .on(Image.circle(20).fillColor(Color.cornflowerBlue))
  .on(Image.circle(30).fillColor(Color.white))
  .on(Image.circle(50).fillColor(Color.darkBlue))
// res0: Image = On(
//   On(
//     On(
//       FillColor(
//         Circle(10.0),
//         RGBA(
//           UnsignedByte(-128),
//           UnsignedByte(-128),
//           UnsignedByte(-128),
//           Normalized(1.0)
//         )
//       ),
//       FillColor(
//         Circle(20.0),
//         RGBA(
//           UnsignedByte(-28),
//           UnsignedByte(21),
//           UnsignedByte(109),
//           Normalized(1.0)
//         )
//       )
//     ),
//     FillColor(
//       Circle(30.0),
//       RGBA(
//         UnsignedByte(127),
//         UnsignedByte(127),
//         UnsignedByte(127),
//         Normalized(1.0)
//       )
//     )
//   ),
//   FillColor(
//     Circle(50.0),
//     RGBA(
//       UnsignedByte(-128),
//       UnsignedByte(-128),
//       UnsignedByte(11),
//       Normalized(1.0)
//     )
//   )
// )

3.4 Creating Colors

We’ve seen how to use predefined colors in our images. What about creating our own colors? In this section we will see how to create colors of our own, and transform existing colors into new ones.

3.4.1 RGB Colors

Computers work with colors defined by mixing together different amounts of red, green, and blue. This “RGB” model is an additive model of color, which means adding more colors gets us closer to white. This is the oppositive of paint, which is a subtractive model where adding more paints gets us closer to black. Each red, green, or blue component can have a value between zero and 255. If all three components are set to the maximum of 255 we get pure white. If all components are zero we get black.

We can create our own RGB colors using the rgb method on the Color object. This method takes three parameters: the red, green, and blue components. These are numbers between 0 and 255, called an UnsignedByte². There is no literal expression for UnsignedByte like there is for Int, so we must convert an Int to UnsignedByte. We can do this with the uByte method. An Int can take on more values that an UnsignedByte, so if the number is too small or too large to be represented as a UnsignedByte it will be converted to the closest values is the range 0 to 255. These examples illustrate the conversion.

0.uByte.get
// res0: Int = 0
255.uByte.get
// res1: Int = 255
128.uByte.get
// res2: Int = 128
-100.uByte.get // Too small, is transformed to 0
// res3: Int = 0 // Too small, is transformed to 0
1000.uByte.get // Too big, is transformed to 255
// res4: Int = 255

(Note that UnsignedByte is a feature of Doodle. It is not something provided by Scala.)

Now we know how to construct UnsignedBytes we can make RGB colors.

Color.rgb(255.uByte, 255.uByte, 255.uByte) // White
Color.rgb(0.uByte, 0.uByte, 0.uByte) // Black
Color.rgb(255.uByte, 0.uByte, 0.uByte) // Red

3.4.2 HSL Colors

The RGB color representation is not very easy to use. The hue-saturation-lightness (HSL) format more closely corresponds to how we perceive color. In this representation a color consists of:

• hue, which is an angle between 0 and 360 degrees giving a rotation around the color wheel.
• saturation, which is a number between 0 and 1 giving the intensity of the color from a drab gray to a pure color; and
• lightness between 0 and 1 giving the color a brightness varying from black to pure white.

fig. 7 shows how colors vary as we change hue and lightness, and fig. 8 shows the effect of changing saturation.

Figure 7: A color wheel showing changes in hue (rotations) and lightness (distance from the center) with saturation fixed at 1.

Figure 8: A gradient showing how changing saturation effects color, with hue and lightness held constant. Saturation is zero on the left and one on the right.

We can construct a color in the HSL representation using the Color.hsl method. This method takes as parameters the hue, saturation, and lightness. The hue is an Angle. We can convert a Double to an Angle using the degrees (or radians) methods.

0.degrees
// res8: Angle = Angle(0.0)
180.degrees
// res9: Angle = Angle(3.141592653589793)
3.14.radians
// res10: Angle = Angle(3.14)

Saturation and lightness are both Doubles that should be between 0.0 and 1.0. Values outside this range will be converted to the closest number within the range.

We can now create colors using the HSL representation.

Color.hsl(0.degrees, 0.8, 0.6) // A pastel red

To view this color we can render it in a picture. See fig. 9 for an example.

Figure 9: Rendering pastel red in a triangle

3.4.3 Manipulating Colors

The effectiveness of a composition often depends as much on the relationships between colors as the actual colors used. Colors have several methods that allow us to create a new color from an existing one. The most commonly used ones are:

• spin, which rotates the hue by an Angle;
• saturate and desaturate, which respectively add and subtract a Normalised value from the color; and
• lighten and darken, which respectively add and subtract a Normalised value from the lightness.

For example,

Image.circle(100)
     .fillColor(Color.red)
     .beside(Image.circle(100).fillColor(Color.red.spin(15.degrees)))
     .beside(Image.circle(100).fillColor(Color.red.spin(30.degrees)))
     .strokeWidth(5.0)

produces fig. 10.

Figure 10: Three circles, starting with Color.red and spinning by 15 degrees for each successive circle

Here’s a similar example, this time manipulating saturation and lightness, shown in fig. 11.

Image.circle(40)
   .fillColor(Color.red.darken(0.2.normalized))
   .beside(Image.circle(40).fillColor(Color.red))
   .beside(Image.circle(40).fillColor((Color.red.lighten(0.2.normalized))))
   .above(Image.rectangle(40, 40).fillColor(Color.red.desaturate(0.6.normalized))
               .beside(Image.rectangle(40,40).fillColor(Color.red.desaturate(0.3.normalized)))
               .beside(Image.rectangle(40,40).fillColor(Color.red)))

Figure 11: The top three circles show the effect of changing lightness, and the bottom three squares show the effect of changing saturation.

3.4.4 Transparency

We can also add a degree of transparency to our colors, by adding an alpha value. An alpha value of 0.0 indicates a completely transparent color, while a color with an alpha of 1.0 is completely opaque. The methods Color.rgba and Color.hsla have a fourth parameter that is a Normalized alpha value. We can also create a new color with a different transparency by using the alpha method on a color. Here’s an example, shown in fig. 12.

Image.circle(40)
     .fillColor(Color.red.alpha(0.5.normalized))
     .beside(Image.circle(40).fillColor(Color.blue.alpha(0.5.normalized)))
     .on(Image.circle(40).fillColor(Color.green.alpha(0.5.normalized)))

Figure 12: Circles with alpha of 0.5 showing transparency

Exercises

Analogous Triangles

Create three triangles, arranged in a triangle, with analogous colors. Analogous colors are colors that are similar in hue. See a (fairly elaborate) example in fig. 13.

Figure 13: Analogous triangles. The colors chosen are variations on darkSlateBlue

Image.triangle(40, 40)
  .strokeWidth(6.0)
  .strokeColor(Color.darkSlateBlue)
  .fillColor(Color.darkSlateBlue
               .lighten(0.3.normalized)
               .saturate(0.2.normalized)
               .spin(10.degrees))
  .above(Image.triangle(40, 40)
           .strokeWidth(6.0)
           .strokeColor(Color.darkSlateBlue.spin(-30.degrees))
           .fillColor(Color.darkSlateBlue
                        .lighten(0.3.normalized)
                        .saturate(0.2.normalized)
                        .spin(-20.degrees))
           .beside(Image.triangle(40, 40)
                     .strokeWidth(6.0)
                     .strokeColor(Color.darkSlateBlue.spin(30.degrees))
                     .fillColor(Color.darkSlateBlue
                                  .lighten(0.3.normalized)
                                  .saturate(0.2.normalized)
                                  .spin(40.degrees))))
// res15: Image = Above(
//   FillColor(
//     StrokeColor(
//       StrokeWidth(Triangle(40.0, 40.0), 6.0),
//       RGBA(
//         UnsignedByte(-56),
//         UnsignedByte(-67),
//         UnsignedByte(11),
//         Normalized(1.0)
//       )
//     ),
//     HSLA(
//       Angle(4.5110048359238055),
//       Normalized(0.5899999999999999),
//       Normalized(0.692156862745098),
//       Normalized(1.0)
//     )
//   ),
//   Beside(
//     FillColor(
//       StrokeColor(
//         StrokeWidth(Triangle(40.0, 40.0), 6.0),
//         HSLA(
//           Angle(3.812873135126074),
//           Normalized(0.3899999999999999),
//           Normalized(0.39215686274509803),
//           Normalized(1.0)
//         )
//       ),
//       HSLA(
//         Angle(3.987406060325507),
//         Normalized(0.5899999999999999),
//         Normalized(0.692156862745098),
//         Normalized(1.0)
//       )
//     ),
//     FillColor(
//       StrokeColor(
//         StrokeWidth(Triangle(40.0, 40.0), 6.0),
//         HSLA(
//           Angle(4.860070686322672),
//           Normalized(0.3899999999999999),
//           Normalized(0.39215686274509803),
//           Normalized(1.0)
//         )
//       ),
//       HSLA(
//         Angle(5.034603611522105),
//         Normalized(0.5899999999999999),
// ...

3.5 Exercises

3.5.1 Compilation Target

Create a line drawing of an archery target with three concentric scoring bands, as shown in fig. 14.

Figure 14: Simple archery target

For bonus credit add a stand so we can place the target on a range, as shown in fig. 15.

Figure 15: Archery target with a stand

Image
  .circle(20)
  .on(Image.circle(40))
  .on(Image.circle(60))

Image
  .circle(20)
  .on(Image.circle(40))
  .on(Image.circle(60))
  .above(Image.rectangle(6, 20))
  .above(Image.rectangle(20, 6))

3.5.2 Stay on Target

Colour your target red and white, the stand in brown (if applicable), and some ground in green. See fig. 16 for an example.

Figure 16: Colour archery target

Image
  .circle(20).fillColor(Color.red)
  .on(Image.circle(40).fillColor(Color.white))
  .on(Image.circle(60).fillColor(Color.red))
  .above(Image.rectangle(6, 20).fillColor(Color.brown))
  .above(Image.rectangle(20, 6).fillColor(Color.brown))
  .above(Image.rectangle(80, 25).noStroke.fillColor(Color.green))

4 Writing Larger Programs

We’re getting to the point where it’s inconvenient to type programs into the console. In this chapter we’ll learn about two tools for writing larger programs:

• saving programs to a file so we don’t have to type code over and over again;
• giving names to values so we can reuse them.

import doodle.core._
import doodle.image._
import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

4.1 Working Within the Console

Your text editor or IDE will allow you to save code to a file, but we need to save files in the right place so the Scala compiler can find them. If you’re working from the Doodle template you should save your code in the directory src/main/scala/.

How do we use code that we saved to a file from the console? There is a special command, that only works from the console, that allows us to run code saved in a file. This command is called :paste³. We follow :paste with the name of the file we want to run. For example, if we save in the file src/main/scala/Example.scala the expression

Image.circle(100).fillColor(Color.paleGoldenrod).strokeColor(Color.indianRed)

we can then run this code by writing at the console

:paste src/main/scala/Example.scala
// res0: doodle.core.Image = ContextTransform(<function1>,ContextTransform(<function1>,Circle(100.0)))

Note the value has been given the name res0 in the example above. If you’re following along, the name in your console might end with a different number depending on what you’ve already typed into the console. We can draw the image by evaluating res0.draw (or the correct name for your console).

4.1.1 Tips for Using the Console

Here are a few tips for using the console more productively:

• If you press the up arrow you’ll get the last thing you typed into the console. Handy to avoid having to type in those long file names over and over again! You can press up multiple times to go through the history of your interactions at the console.

• You can press the Tab key to get the console to suggest completions for code, but unfortunately not file names, you’re typing. For example, if you type Stri and then press Tab, the console will show possible completions. Type Strin and the console will complete String for you.

4.2 Coding Outside the Console

The code we’ve been writing inside the console will cause problems running outside the console. For example, put the following code into Example.scala in the src/main/scala.

Image.circle(100).fillColor(Color.paleGoldenrod).strokeColor(Color.indianRed)

Now restart SBT and try to enter the console. You should see an error similar to

[error] src/main/scala/Example.scala:1: expected class or object definition
[error] circle(100) fillColor Color.paleGoldenrod strokeColor Color.indianRed
[error] ^
[error] one error found

You’ll see something similar if you’re using an IDE.

The problem is this:

• Scala is attempting to compile all our code before the console starts; and
• there are restrictions on code written in files that don’t apply to code written directly in the console.

We need to know about these restrictions and change how we write code in files accordingly.

The error message gives us some hint: expected class or object definition. We don’t yet know what a class is, but we do know about objects—all values are objects. In Scala all code in a file must be written inside an object or class. We can easily define an object by wrapping an expression like the below.

object Example {
  Image.circle(100).fillColor(Color.paleGoldenrod).strokeColor(Color.indianRed).draw()
}

Now the code won’t compile for a different reason. You should see a lot of errors similar to

[error] doodle/shared/src/main/scala/doodle/examples/Example.scala:1: not found: value Image
[error]   Image.circle(100).fillColor(Color.paleGoldenrod).strokeColor(Color.indianRed).draw()
[error]   ^

The compiler is saying that we’ve used a name, circle, but the compiler doesn’t know what value this name refers to. It will have a similiar issue with Color in the code above. We’ll talk in more details about names in just a moment. Right now let’s tell the compiler where it can find the values for these names by adding some import statements. The name Color is found inside a package called doodle.core, and the name circle is within the object Image that is in doodle.image. We can tell the compiler to use all the name in doodle.core, and all the names in doodle.image by writing

import doodle.core._
import doodle.image._

There are a few other names that the compiler will need to find for the complete code to work. We can import these with the lines

import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

We should place all these imports at the top of the file, so the complete code looks like

import doodle.core._
import doodle.image._
import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

object Example {
  Image.circle(100).fillColor(Color.paleGoldenrod).strokeColor(Color.indianRed).draw()
}

With this in place the code should compile without issue.

Now when we go to the console within SBT we can refer to our code using the name, Example, that we’ve given it.

Example // draws the image

Exercise

If you haven’t done so already, save the code above in the file src/main/scala/Example.scala and check that the code compiles and you can access it from the console.

4.3 Names

In the previous section we introduced a lot of new concepts. In this section we’ll explore one of those concepts: naming values.

We use names to refer to things. For example, “Professeur Emile Perrot” refers to a very fragrant rose variety, while “Cherry Parfait” is a highly disease resistant variety but barely smells at all. Much ink has been spilled, and many a chin stroked, on how exactly this relationship works in spoken language. Programming languages are much more constrained, which allows us to be much more precise: names refer to values. We will sometimes say names are bound to values, or a name introduces a binding. Wherever we would write out a value we can instead use its name, if the value has a name. In other words, a name evaluates to the value it refers to. This naturally raises the question: how do we give names to values? There are several ways to do this in Scala. Let’s see a few.

4.3.1 Object Literals

We have already seen an example of declaring an object literal.

object Example {
  Image.circle(100).fillColor(Color.paleGoldenrod).strokeColor(Color.indianRed).draw()
}

This is a literal expression, like other literals we’ve seen so far, but in this case it creates an object with the name Example. When we use the name Example in a program it evaluates to that object.

Example
// Example.type = Example$@76c39258

Try this in the console a few times. Do you notice any difference in uses of the name? You might have noticed that the first time you entered the name Example a picture was drawn, but on subsequent uses this didn’t happen. The first time we use an object’s name the body of the object is evaluated and the object is created. On subsequent uses of the name the object already exists and is not evaluated again. We can tell there is a difference in this case because the expression inside the object calls the draw method. If we replaced it with something like 1 + 1 (or just dropped the call to draw) we would not be able to tell the difference. We’ll have plenty more to say about this in a later chapter.

We might wonder about the type of the object we’ve just created. We can ask the console about this.

:type Example
// Example.type

The type of Example is Example.type, a unique type that no other value has.

4.3.2 val Declarations

Declaring an object literal mixes together object creation and defining a name. It would be useful if we could separate the two, so we could give a name to a pre-existing object. A val declaration allows us to do this.

We use val by writing

val <name> = <value>

replacing <name> and <value> with the name and the expression evaluating to the value respectively. For example

val one = 1
val anImage = Image.circle(100).fillColor(Color.red)

These two declarations define the names one and anImage. We can use these names to refer to the values in later code.

one
// res0: Int = 1
anImage
// res1: Image = FillColor(
//   Circle(100.0),
//   RGBA(
//     UnsignedByte(127),
//     UnsignedByte(-128),
//     UnsignedByte(-128),
//     Normalized(1.0)
//   )
// )

4.3.3 Declarations

We’ve talked about declarations and definitions above. It’s now time to be precise about what these terms mean, and to look in a bit more depth at the differences between object and val.

We already know about expressions. They are a part of a program that evaluates to a value. A declaration or definition is another part of a program, but do not evaluate to a value. Instead they give a name to something—not always to a value as you can declare types in Scala, though we won’t spend much time on this. Both object and val are declarations.

One consequence of declarations being separate from expressions is we can’t write program like

val one = ( val aNumber = 1 )

because val aNumber = 1 is not an expression and thus does not evaluate to a value.

We can however write

val aNumber = 1
// aNumber: Int = 1
val one = aNumber
// one: Int = 1

4.3.4 The Top-Level

It seems a bit unsatisfactory to have both object and val declarations, as they both give names to values. Why not just have val for declaring names, and make object just create objects without naming them? Can you declare an object literal without a name?

object {}

Scala distinguishes between what is called the top-level and other code. Code at the top-level is code that doesn’t have any other code wrapped around. In other words it is something we can write in a file and Scala will compile without having to wrap it in an object.

We’ve seen that expressions aren’t allowed at the top-level. Neither are val definitions. Object literals, however, are.

This distinction is a bit annoying. Some other languages don’t have this restriction. In Scala’s case it comes about because Scala builds on top of the Java Virtual Machine (JVM), which was designed to run Java code. Java makes a distinction between top-level and other code, and Scala is forced to make this distinction to work with the JVM. The Scala console doesn’t make this top-level distinction (we can think of everything written in the console being wrapped in some object) which can lead to confusion when we first start using Scala.

If an object literal is allowed at the top-level, but a val definition is not, does this mean we can declare a val inside an object literal? If we can declare a val inside an object literal, can we later refer to that name?

object Example {
  val hi = "Hi!"
}

Example.hi
// res4: String = "Hi!"

hi
// error: not found: value hi

4.3.5 Scope

If you did the last exercise (and you did, didn’t you?) you’ll have seen that a name declared inside an object can’t be used outside the object without also referring to the object that contains the name. Concretely, if we declare

object Example {
  val hi = "Hi!"
}

we can’t write

hi
// error: not found: value hi

We must tell Scala to look for hi inside Example.

Example.hi
// res8: String = "Hi!"

We say that a name is visible in the places where it can be used without qualification, and we call the places where a name is visible its scope. So using our fancy-pants new terminology, hi is not visible outside of Example, or alternatively hi is not in scope outside of Example.

How do we work out the scope of a name? The rule is fairly simple: a name is visible from the point it is declared to the end of the nearest enclosing braces (braces are { and }). In the example above hi is enclosed by the braces of Example and so is visible there. It’s not visible elsewhere.

We can declare object literals inside object literals, which allows us to make finer distinctions about scope. For example in the code below

object Example1 {
  val hi = "Hi!"

  object Example2 {
    val hello = "Hello!"
  }
}

hi is in scope in Example2 (Example2 is defined within the braces that enclose hi). However the scope of hello is restricted to Example2, and so it has a smaller scope than hi.

What happens if we declare a name within a scope where it is already declared? This is known as shadowing. In the code below the definition of hi within Example2 shadows the definition of hi in Example1

object Example1 {
  val hi = "Hi!"

  object Example2 {
    val hi = "Hello!"
  }
}

Scala let’s us do this, but it is generally a bad idea as it can make code very confusing.

We don’t have to use object literals to create new scopes. Scala allows us to create a new scope just about anywhere by inserting braces. So we can write

object Example {
  val good = "Good"

  // Create a new scope
  {
    val morning = good ++ " morning"
    val toYou = morning ++ " to you"
  }

  val day = good ++ " day, sir!"
}

morning (and toYou) is declared within a new scope. We have no way to refer to this scope from the outside (it has no name) so we cannot refer to morning outside of the scope where it is declared. If we had some secrets that we didn’t want the rest of the program to know about this is one way we could hide them.

The way nested scopes work in Scala is called lexical scoping. Not all languages have lexical scoping. For example, Ruby and Python do not, and Javascript has only recently acquired lexical scoping. It is the authors’ opinion that creating a language without lexical scope is an idea on par with eating a bushel of Guatemalan insanity peppers and then going to the toilet without washing your hands.

Exercises

Test your understanding of names and scoping by working out the value of answer in each case below.

val a = 1
val b = 2
val answer = a + b

object One {
  val a = 1

  object Two {
    val a = 3
    val b = 2
  }

  object Answer {
    val answer = a + Two.b
  }
}

object One {
  val a = 5
  val b = 2

  object Answer {
    val a = 1
    val answer = a + b
  }
}

object One {
  val a = 1
  val b = a + 1
  val answer = a + b
}

object One {
  val a = 1

  object Two {
    val b = 2
  }

  val answer = a + b
}

object One {
  val a = b - 1
  val b = a + 1

  val answer = a + b
}

4.4 Abstraction

We’ve learned a lot about names in the previous section. If we want to use fancy programmer words, we could say that names abstract over expressions. This usefully captures the essence of what defining names does, so let’s decode the programmer-talk.

To abstract means to remove unnecessary details. For example, numbers are an abstraction. The number “one” is never found in nature as a pure concept. It’s always one object, such as one apple, or one copy of Creative Scala. When doing arithmetic the concept of numbers allows us to abstract away the unnecessary detail of the exact objects we’re counting and manipulate the numbers on their own.

Similarly a name stands in for an expression. An expression tells us how to construct a value. If that value has a name then we don’t need to know anything about how the value is constructed. The expression can have arbitrary complexity, but we don’t have to care about this complexity if we just use the name. This is what it means when we say that names abstract over expressions. Whenever we have an expression we can substitute a name that refers to the same value.

Abstraction makes code easier to read and write. Let’s take as an example creating a sequence of boxes like shown in fig. 17.

Figure 17: Five boxes filled with Royal Blue

We can write out a single expression that creates the picture.

Image.rectangle(40, 40)
     .strokeWidth(5.0)
     .strokeColor(Color.royalBlue.spin(30.degrees))
     .fillColor(Color.royalBlue)
     .beside(
       Image.rectangle(40, 40)
         .strokeWidth(5.0)
         .strokeColor(Color.royalBlue.spin(30.degrees))
         .fillColor(Color.royalBlue)
     ).beside(
        Image.rectangle(40, 40)
          .strokeWidth(5.0)
          .strokeColor(Color.royalBlue.spin(30.degrees))
          .fillColor(Color.royalBlue)
     ).beside(
        Image.rectangle(40, 40)
             .strokeWidth(5.0)
             .strokeColor(Color.royalBlue.spin(30.degrees))
            .fillColor(Color.royalBlue)
     ).beside(
        Image.rectangle(40, 40)
             .strokeWidth(5.0)
             .strokeColor(Color.royalBlue.spin(30.degrees))
             .fillColor(Color.royalBlue)
     )

In this code it is difficult to see the simple pattern within. Can you really tell at a glance that all the rectangles are exactly the same? If we make the abstraction of naming the basic box the code becomes much easier to read.

val box =
  Image.rectangle(40, 40)
       .strokeWidth(5.0)
       .strokeColor(Color.royalBlue.spin(30.degrees))
       .fillColor(Color.royalBlue)

box.beside(box).beside(box).beside(box).beside(box)

Now we can easily see how the box is made, and easily see that the final picture is that box repeated five times.

Exercises

Archery Again

Let’s return to the archery target we created in an earlier chapter, shown in fig. 18.

Figure 18: The Archery Target

Last time we created the image we didn’t know how to name values, so we can to write one large expression. This time around, give the components of the image names so that it is easier for someone else to understand how the image is constructed. You’ll have to use your own taste to decide what parts should be named and what parts don’t warrant names of their own.

val coloredTarget =
  (
    Image.circle(10).fillColor(Color.red) on
      Image.circle(20).fillColor(Color.white) on
      Image.circle(30).fillColor(Color.red)
  )

val stand =
  Image.rectangle(6, 20) above Image.rectangle(20, 6).fillColor(Color.brown)

val ground =
  Image.rectangle(80, 25).strokeWidth(0).fillColor(Color.green)

val image = coloredTarget above stand above ground

Streets Ahead

For a more compelling use of names, create a street scene like that shown in fig. 19. By naming the individual components of the image you should be able to avoid a great deal of repetition.

Figure 19: A Street Scene

val roof = Image.triangle(50, 30) fillColor Color.brown

val frontDoor =
  (Image.rectangle(50, 15) fillColor Color.red) above (
    (Image.rectangle(10, 25) fillColor Color.black) on
    (Image.rectangle(50, 25) fillColor Color.red)
  )

val house = roof above frontDoor

val tree =
  (
    (Image.circle(25) fillColor Color.green) above
    (Image.rectangle(10, 20) fillColor Color.brown)
  )

val streetSegment =
  (
    (Image.rectangle(30, 3) fillColor Color.yellow) beside
    (Image.rectangle(15, 3) fillColor Color.black) above
    (Image.rectangle(45, 7) fillColor Color.black)
  )

val street = streetSegment beside streetSegment beside streetSegment

val houseAndGarden =
  (house beside tree) above street

val image = (
  houseAndGarden beside
  houseAndGarden beside
  houseAndGarden
) strokeWidth 0

4.5 Packages and Imports

When we changed our code to compile we had to add many import statements to it. In this section we learn about them.

We’ve seen that one name can shadow another. This can cause problems in larger programs as many parts of a program many want to put a common name to different uses. We can create scopes to hide names from the outside, but we must still deal with names defined at the top-level.

We have the same problem in natural language. For example, if both your brother and friend were called “Ziggy” you would have to qualify which one you meant when you used their name. Perhaps you could tell from context, or perhaps your friend was “Ziggy S” and your brother was just “Ziggy”.

In Scala we can use packages to organise names. A package creates a scope for names defined at the top-level. All top-level names within the same package are defined in the same scope. To bring names in a package into another scope we must import them.

Creating a package is simple: we write

package <name>

at the top of the file, replace <name> with the name of our package.

When we want to use names defined in a package we use an import statement, specifying the package name followed by _ for all names, or the just the name we want if we only want one or a few names.

Here’s an example.

Let’s start by defining some names within a package.

package example

object One {
  val one = 1
}

object Two {
  val two = 2
}

object Three {
  val three = 3
}

Now to bring these names into scope we must import them. We could import just one name.

import example.One

One.one

Or both One and Two.

import example.{One, Two}

One.one + Two.two

Or all the names in example.

import example._

One.one + Two.two + Three.three

In Scala we can also import just about anything that defines a scope, including objects. So the following code brings one into scope.

import example.One._

one

4.5.1 Package Organisation

Packages stop top-level names from colliding, but what about collisions between package names? It’s common to organise packages in a hierarchy, which helps to avoid collisions. For example, in Doodle the package core is defined within the package doodle. When we use the statement

import doodle.core._

we’re indicating we want the package core within the package doodle, and not some other package that might be called core.

5 The Substitution Model of Evaluation

We need to build a mental model of how Scala expressions are evaluated so we can understand what our programs are doing. We’ve been getting by with an informal model so far. In this section we make our model a bit more formal by learning about the substitution model of evaluation. Like many things in programming we’re using some fancy words for a simple concept. In this case you’ve probably already learned about substitution in high school algebra, and we’re just taking those ideas into a new context.

import doodle.core._
import doodle.image._
import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

5.1 Substitution

Substitution says that wherever we see an expression we can replace it with the value it evaluates to. For example, where we see

1 + 1

we can replace it with 2. This in turn means when we see a compound expression such as

(1 + 1) + (1 + 1)

we can substitute 2 for 1 + 1 giving

2 + 2

which evaluates to 4.

This type of reasoning is what we do in high school algebra when we simplify an expression. Naturally computer science has fancy words for this process. In addition to substitution, we can call this reducing an expression, or equational reasoning.

Substitution gives us a way to reason about our programs, which is another way of saying “working out what they do”. We can apply substitution to just about any expression we’ve seen so far. It’s easier to use examples that work with numbers and strings, rather than images, here so we’ll return to an example we saw in an earlier chapter:

1 + ("Moonage daydream".indexOf("N"))

In the previous example we were a bit fast-and-loose. Here we will be a bit more precise to illustrate the steps the computer would have to go through. We are trying to emulate the computer, after all.

The expression containing the + consists of two sub-expressions, 1 and ("Moonage daydream".indexOf("N")). We have to decide which to evaluate first: the left or the right. Let’s arbitrarily choose the right sub-expression (we’ll return to this choice later.)

The sub-expression ("Moonage daydream".indexOf("N")) again consists of two sub-expressions, "Moonage daydream" and "N". Let’s again evaluate the right-hand first, remembering that literal expressions are not values so they must be evaluated.

The literal "N" evaluates to the value "N". To avoid this confusion let’s write the value as |"N"|. Now we can substitute the value for the expression given in our first steps

1 + ("Moonage daydream".indexOf(|"N"|))

Now we can evaluate the left-hand side of the sub-expression, substituting the literal expression "Moonage daydream" with its value |"Moonage daydream"|. This gives us

1 + (|"Moonage daydream"|.indexOf(|"N"|))

Now we’re in a position to evaluate the entire expression (|"Moonage daydream"|.indexOf(|"N"|)), which evaluates to |-1| (again differentiating the integer value from the literal expression by using a vertical bar). Once again we perform substitution and now we have

1 + |-1|

Now we should evaluate the left-hand side literal 1, giving |1|. Perform substitution and we get

|1| + |-1|

Now we can evaluate the entire expression, giving

|0|

We can ask Scala to evaluate the whole expression to check our work.

1 + ("Moonage daydream".indexOf("N"))
// res4: Int = 0

Correct!

There are some observations we might make at this point:

• doing substitution rigorously like a computer might involve a lot of steps;
• the shortcut evaluation you probably did in your head probably got to the correct answer; and
• our seemingly arbitrary choice to do evaluation from right-to-left got us the correct answer.

Did we somehow manage to choose the same substitution order that Scala uses (no we didn’t, but we haven’t investigated this yet) or does it not really matter what order we choose? When exactly can we take shortcuts and still reach the right result, like we did in the first example with addition? We will investigate these questions in just a moment, but first let’s talk about how substitution works with names.

5.1.1 Names

The substitution rule for names is to substitute the name with the value it refers to. We’ve already been using this rule implicitly. Now we’re just formalising it.

For example, given the code

val name = "Ada"
name ++ " " ++ "Lovelace"

we can apply substitution to get

"Ada" ++ " " ++ "Lovelace"

which evaluates to

"Ada Lovelace"

We can use names to be a bit more formal with our substitution process. Returning to our first example

1 + 1

we can give this expression a name:

val two = 1 + 1

When we see a compound expression such as

(1 + 1) + (1 + 1)

substitution tells us we can substitute two for 1 + 1 giving

two + two

Remember when we worked through the expression

1 + ("Moonage daydream".indexOf("N"))

we broke it into sub-expressions which we then evaluated and substituted. Using words, this was quite convoluted. With a few val declarations we can make this both more compact and easier to see. Here’s the same expression broken into it’s components.

val a = 1
val b = "Moonage daydream"
val c = "N"
val d = b.indexOf(c)
val e = a + d

If we (at this point, arbitrarily) define that evaluation occurs from top-to-bottom we can experiment with different ordering to see what difference they make.

For example,

val c = "N"
val b = "Moonage daydream"
val a = 1
val d = b.indexOf(c)
val e = a + d

achieves the same result as before. However we can’t use

val e = a + d
val a = 1
val b = "Moonage daydream"
val c = "N"
val d = b.indexOf(c)

because e depends on a and d, and in our top-to-bottom ordering a and d have yet to be evaluated. We might rightly claim that this is a bit silly to even attempt. The complete expression we’re trying to evaluate is e but a to d are sub-expressions of e, so of course we have to evaluate the sub-expressions before we evaluate the expression.

5.2 Order of Evaluation

We’re now ready to tackle the question of order-of-evaluation. We might wonder if the order of evaluation even matters? In the examples we’ve looked at so far the order doesn’t seem to matter, except for the issue that we cannot evaluate an expression before it’s sub-expressions.

To investigate these issues further we need to introduce a new concept. So far we have almost always dealt with pure expressions. These are expressions that we can freely substitute in any order without issue⁴.

Impure expressions are those where the order of evaluation matters. We have already used one impure expression, the method draw. If we evaluate

Image.circle(100).draw
Image.rectangle(100, 50).draw

and

Image.rectangle(100, 50).draw
Image.circle(100).draw

the windows containing the images will appear in different orders. Hardly an exciting difference, but it is a difference, which is the point.

The key distinguishing feature of impure expressions is that their evaluation causes some change that we can see. For example, evaluating draw causes an image to be displayed. We call these observable changes side effects, or just effects for short. In a program containing side effects we cannot freely use substitution. However we can use side effects to investigate the order of evaluation. Our tool for doing so will be the println method.

The println method displays text on the console (a side effect) and evaluates to unit. Here’s an example:

println("Hello!")
// Hello!

The side-effect of println—printing to the console—gives us a convenient way to investigate the order of evaluation. For example, the result of running

println("A")
// A
println("B")
// B
println("C")
// C

indicates to us that expressions are evaluated from top to bottom. Let’s use println to investigate further.

Exercises

No Substitute for Println

In a pure program we can give a name to any expression and substitute any other occurrences of that expression with the name. Concretely, we can rewrite

(2 + 2) + (2 + 2)

to

val a = (2 + 2)
a + a

and the result of the program doesn’t change.

Using println as an example of an impure expression, demonstrates that this is not the case for impure expressions, and hence we can say that impure expressions, or side effects, break substitution.

println("Happy birthday to you!")
// Happy birthday to you!
println("Happy birthday to you!")
// Happy birthday to you!
println("Happy birthday to you!")
// Happy birthday to you!

val happy = println("Happy birthday to you!")
// Happy birthday to you!
happy
happy
happy

Madness to our Methods

When we introduced scopes we also introduced block expressions, though we didn’t call them that at the time. A block is created by curly braces ({}). It evaluates all the expressions inside the braces. The final result is the result of the last expression in the block.

// Evaluates to three
{
  val one = 1
  val two = 2
  one + two
}
// res12: Int = 3

We can use block expressions to investigate the order in which method parameters are evaluated, by putting println expression inside a block that evaluates to some other useful value.

For example, using Image.rectangle or Color.hsl and block expressions, we can determine if Scala evaluates method parameters in a fixed order, and if so what that order is.

Note that you can write a block compactly, on one line, by separating expressions with semicolons (;). This is generally not good style but might be useful for these experiments. Here’s an example.

// Evaluates to three
{ val one = 1; val two = 2; one + two }
// res13: Int = 3

Color.hsl(
  {
    println("a")
    0.degrees
  },
  {
    println("b")
    1.0
  },
  {
    println("c")
    1.0
  }
)
// a
// b
// c
// res14: Color = HSLA(
//   Angle(0.0),
//   Normalized(1.0),
//   Normalized(1.0),
//   Normalized(1.0)
// )

Color.hsl({ println("a"); 0.degrees },
          { println("b"); 1.0 },
          { println("c"); 1.0 })
// a
// b
// c
// res15: Color = HSLA(
//   Angle(0.0),
//   Normalized(1.0),
//   Normalized(1.0),
//   Normalized(1.0)
// )

The Last Order

In what order are Scala expressions evaluated? Perform whatever experiments you need to determine an answer to this question to your own satisfaction. You can reasonably assume that Scala uses consistent rules across all expressions. There aren’t special cases for different expressions.

{ println("a"); 1 } + { println("b"); 2 } + { println("c"); 3}
// a
// b
// c
// res16: Int = 6

5.3 Local Reasoning

We’ve seen that the order of evaluation is only really important when we have side effects. For example, if the following expressions produce side effects

disableWarheads()
launchTheMissles()

we really want to ensure that the expressions are evaluated top to bottom so the warheads are disabled before the missles are launched.

All useful programs must have some effect, because effects are how the program interacts with the outside world. The effect might just be printing out something when the program has finished, but it’s still there. Minimising side effects is a key goal of functional programming so we will spend a few more words on this topic.

Substitution is really easy to understand. When the order of evaluation doesn’t matter it means any other code cannot change the meaning of the code we’re looking at. 1 + 1 is always 2, no matter what other code we have in our program, but the effect of launchTheMissles() depends on whether we have already disabled the warheads or not.

The upshot of this is that pure code can be understood in isolation. Since no other code can change its meaning, if we’re only interested in one fragment we can ignore the rest of the code. The meaning of impure code, on the other hand, depends on all the code that will have run before it is evaluated. This property is known as local reasoning. Pure code has it, but impure code does not.

As programs get larger it becomes harder and harder to keep all the details in our head. Since the size of our head is a fixed quantity the only solution is to introduce abstraction. Remember that an abstraction is the removal of irrelevant details. Pure code is the ultimate abstraction, because it tells us that everything else is an irrelevant detail. This is one of the properties that gets functional programmers really excited: the ability to make large programs understandable. Functional programming doesn’t mean avoiding effects, because all useful programs have effects. It does, however, mean controlling effects so the majority of the code can be reasoned about using the simple model of substitution.

5.3.1 The Meaning of Meaning

So far, we’ve talked a lot about the meaning of code, where we’ve taken “meaning” to mean to the result it evaluates to, and perhaps the side effects it performs.

In substitution, the meaning of a program is exactly what it evaluates to. Thus two programs are equal if they evaluate to the same result. This is precisely why side effects break substitution: the substitution model has no notion of side effects and therefore cannot distinguish two programs that differ by their effects.

There are other ways in which programs can differ. For example, one program may take longer than another to produce the same result. Again, substitution does not distinguish them.

Substitution is an abstraction, and the details it throws away are everything except for the value. Side effects, time, and memory usage are all irrelevant to substitution, but perhaps not to the people writing or running the program. There is a tradeoff here. We can employ richer models that capture more of these details, but they are much harder to work with. For most people most of the time substitution makes the right tradeoff of being dead simple to use while still being useful.

6 Methods

We’ve already used methods—methods are the way we interact with objects. In this chapter we’ll learn how to write our own methods.

Names allow us to abstract over expressions. Methods allow us to abstract over and generalise expressions. By generalisation we mean the ability to express a group of related things, in this case expressions. A method captures a template for an expression, and allows the caller to fill in parts of that template by passing the method parameters.

import doodle.core._
import doodle.image._
import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

6.1 Methods

In a previous chapter we created the image shown in fig. 20 using the program

Figure 20: Five boxes filled with Royal Blue

val box =
  Image.rectangle(40, 40).
    strokeWidth(5.0).
    strokeColor(Color.royalBlue.spin(30.degrees)).
    fillColor(Color.royalBlue)

box beside box beside box beside box beside box

Imagine we wanted to change the color of the boxes. Right now we would have to write out the expression again for each different choice of color.

val paleGoldenrod = {
  val box =
    Image.rectangle(40, 40).
      strokeWidth(5.0).
      strokeColor(Color.paleGoldenrod.spin(30.degrees)).
      fillColor(Color.paleGoldenrod)

  box beside box beside box beside box beside box
}

val lightSteelBlue = {
  val box =
    Image.rectangle(40, 40).
      strokeWidth(5.0).
      strokeColor(Color.lightSteelBlue.spin(30.degrees)).
      fillColor(Color.lightSteelBlue)

  box beside box beside box beside box beside box
}

val mistyRose = {
  val box =
    Image.rectangle(40, 40).
      strokeWidth(5.0).
      strokeColor(Color.mistyRose.spin(30.degrees)).
      fillColor(Color.mistyRose)

  box beside box beside box beside box beside box
}

This is tedious. Each expression only differs in a minor way. It would be nice if we could capture the general pattern and allow the color to vary. We can do exactly this by declaring a method.

def boxes(color: Color): Image = {
  val box =
    Image.rectangle(40, 40).
      strokeWidth(5.0).
      strokeColor(color.spin(30.degrees)).
      fillColor(color)

  box beside box beside box beside box beside box
}

// Create boxes with different colors
boxes(Color.paleGoldenrod)
boxes(Color.lightSteelBlue)
boxes(Color.mistyRose)

Try this yourself to see that you get the same result using the method as you did writing everything out by hand.

Now that we’ve seen an example of declaring a method, we need to explain the syntax of methods. Next, we’ll look at how to write methods, the semantics of method calls, and how they work in terms of substitution.

6.2 Method Syntax

We’ve already seen an example of declaring a method.

def boxes(color: Color): Image = {
  val box =
    Image.rectangle(40, 40).
      strokeWidth(5.0).
      strokeColor(color.spin(30.degrees)).
      fillColor(color)

  box beside box beside box beside box beside box
}

Let’s use this as a model for understanding the syntax of declaring a method. The first part is the keyword def. A keyword is a special word that indicates something important to the Scala compiler—in this case that we’re going to declare a method. We’re already seen the object and val keywords.

The def is immediately followed by the name of the method, in this case boxes, in the same way that val and object are immediately followed by the name they declare. Like a val declaration, a method declaration is not a top-level declaration and must be wrapped in an object declaration (or other top-level declaration) when written in a file.

Next we have the method parameters, defined in brackets (()). The method parameters are the parts that the caller can “plug-in” to the expression that the method evaluates. When declaring method parameters we must give them both a name and a type. A colon (:) separates the name and the type. We haven’t had to declare types before. Most of the time Scala will work out the types for us, a process known as type inference. Type inference, however, cannot infer the type of method parameters so we must provide them.

After the method parameters comes the result type. The result type is the type of the value the method evaluates to when it is called. Unlike parameter types Scala can infer the result type, but it is good practice to include it and we will do so throughout Creative Scala.

Finally, the body expression of the method calculates the result of calling the method. A body can be a block expression, as in boxes above, or just a single expression.

def methodName(param1: Param1Type, ...): ResultType =
  bodyExpression

Exercises

Let’s practice declaring methods by writing some simple examples.

Square

Write a method square that accepts an Int argument and returns the Int square of it’s argument. (Squaring a number is multiplying it by itself.)

def square(x: Int): Int =
  x * x

def square(x: Int): Int =
  ???

Halve

Write a method halve that accepts a Double argument and returns the Double that is half of it’s argument.

def halve(x: Double): Double =
 x / 2.0

6.3 Method Semantics

Now that we know how to declare methods, let’s turn to the semantics. How do we understand a method call in terms of our substitution model?

We already know we can substitute a method call with the value it evaluates to. However we need a more fine-grained model so we can work out what this value will be. Our extended model is as follows: when we see a method call we will create a new block and within this block: bind the parameters to the respective expressions given in the method call and substitute the method body.

We can then apply substitution as usual.

Let’s see a simple example. Given the method

def square(x: Int): Int =
  x * x

we can expand the method call

square(2)

by introducing a block

{
  square(2)
}

binding the parameter x to the expression 2

{
  val x = 2
  square(2)
}

and substituting the method body

{
  val x = 2
  x * x
}

We can now perform substitution as usual giving

{
  2 * 2
}

and finally

{
  4
}

Once again we see that substitution is involved but no single step was particularly difficult.

Exercise

Last time we looked at substitution we spent a lot of time investigating order of evaluation. In the description above we have decided that a method’s arguments are evaluated before the body is evaluated. This is not the only possibility. We could, for example, evaluate the method’s arguments only at the point they are needed. This could save us some time if a method doesn’t use one of its parameters. By using our old friend println, determine when method parameters are evaluated in Scala.

def example(a: Int, b: Int): Int = {
  println("In the method body!")
  a + b
}

example({ println("a"); 1 }, { println("b"); 2 })
// a
// b
// In the method body!
// res6: Int = 3

6.4 Conclusions

In this chapter, we learned how to write our own simple methods and we saw how to use the substitution model of evaluation to understand method calls.

We saw that methods both abstract over expressions, in the same way as names, and also generalize over expressions, allowing us to represent a group of related expressions with one name.

We wrote some interesting methods, but we still have more repeated code than is desirable (think about the repeated calls to box and circle in the exercises.) In the next chapter, we will learn how we can generalize over this using structural recursion over the natural numbers.

7 Structural Recursion

In this chapter we see our first major pattern for structuring computations: structural recursion over the natural numbers. That’s quite a mouthful, so let’s break it down:

• By a pattern, we mean a way of writing code that is useful in lots of different contexts. We’ll encounter structural recursion in many different situations throughout this book.

• By the natural numbers we mean the whole numbers 0, 1, 2, and upwards.

• By recursion we mean something that refers to itself. Structural recursion means a recursion that follows the structure of the data it is processing. If the data is recursive (refers to itself) then the structural recursion will also refer to itself. We’ll see in more detail what this means in a moment.

import doodle.core._
import doodle.image._
import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

7.1 A Line of Boxes

Let’s start with an example, drawing a line or row of boxes as in fig. 21.

Figure 21: Five boxes filled with Royal Blue

Let’s define a box to begin with.

val aBox = Image.square(20).fillColor(Color.royalBlue)

Then one box in a row is just

val oneBox = aBox

If we want to have two boxes side by side, that is easy enough.

val twoBoxes = aBox.beside(oneBox)

Similarly for three.

val threeBoxes = aBox.beside(twoBoxes)

And so on for as many boxes as we care to create.

You might think this is an unusual way to create these images. Why not just write something like this, for example?

val threeBoxes = aBox.beside(aBox).beside(aBox)

These two definitions are equivalent. We’ve chosen to write later images in terms of earlier ones to emphasise the structure we’re dealing with, which is building up to structural recursion.

Writing images in this way could get very tedious. What we’d really like is some way to tell the computer the number of boxes we’d like. More technically, we would like to abstract over the expressions above. We learned in the previous chapter that methods abstract over expressions, so let’s try to write a method to solve this problem.

We’ll start by writing a method skeleton that defines, as usual, what goes into the method and what it evaluates to. In this case we supply an Int count, which is the number of boxes we want, and we get back an Image.

def boxes(count: Int): Image =
  ???

Now comes the new part, the structural recursion. We noticed that threeBoxes above is defined in terms of twoBoxes, and twoBoxes is itself defined in terms of box. We could even define box in terms of no boxes, like so:

val oneBox = aBox.beside(Image.empty)

Here we used Image.empty to represent no boxes.

Imagine we had already implemented the boxes method. We can say the following properties of boxes always hold, if it is correctly implemented:

• boxes(0) == Image.empty
• boxes(1) == aBox.beside(boxes(0))
• boxes(2) == aBox.beside(boxes(1))
• boxes(3) == aBox.beside(boxes(2))

The last three properties all have the same general shape. We can describe all of them, and any case for n > 0, with the single property boxes(n) == aBox.beside(boxes(n - 1)). So we’re left with two properties

• boxes(0) == Image.empty
• boxes(n) == aBox.beside(boxes(n-1))

These two properties completely define the behavior of boxes. In fact we can implement boxes by converting these properties into code.

A full implementation of boxes is

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox.beside(boxes(n-1))
  }

Try it and see what results you get! This implementation is only tiny bit more verbose than the properties we wrote above, and is our first structural recursion over the natural numbers.

At this point we have two questions to answer. Firstly, how does this match expression work? More importantly, is there some general principle we can use to create methods like this on our own? Let’s take each question in turn.

Exercise: Stacking Boxes

Even before we get into the details of match expressions you should be able to modify boxes to produce an image like fig. 22.

At this point we’re trying to get used to the syntax of match, so rather than copying and pasting boxes write it all out by hand again to get some practice.

Figure 22: Three stacked boxes filled with Royal Blue

def stackedBoxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox.beside(stackedBoxes(n-1))
  }

7.2 Match Expressions

In the previous section we saw the match expression

count match {
  case 0 => Image.empty
  case n => aBox.beside(boxes(n-1))
}

How are we to understand this new kind of expression, and write our own? Let’s break it down.

The very first thing to say is that match is indeed an expression, which means it evaluates to a value. If it didn’t, the boxes method would not work!

To understand what it evaluates to we need more detail. A match expression in general has the shape

<anExpression> match {
  case <pattern1> => <expression1>
  case <pattern2> => <expression2>
  case <pattern3> => <expression3>
  ...
}

<anExpression>, concretely count in the case above, is the expression that evaluates to the value we’re matching against. The patterns <pattern1> and so on are matched against this value. So far we’ve seen two kinds of patterns:

• a literal (as in case 0) which matches exactly the value that literal evaluates to; and
• a wildcard (as in case n) which matches anything, and introduces a binding within the right-hand side expression.

Finally, the right-hand side expressions, <expression1> and so on, are just expressions like any other we’ve written so far. The entire match expression evaluates to the value of the right-hand side expression of the first pattern that matches. So when we call boxes(0) both patterns will match (because the wildcard matches anything), but because the literal pattern comes first the expression Image.empty is the one that is evaluated.

A match expression that checks for all possible cases is called an exhaustive match. If we can assume that count is always greater or equal to zero, the match in boxes is exhaustive.

Once we’re comfortable with match expressions we need to look at the structure of the natural numbers before we can explain structural recursion over them.

Exercises

Guess the Result

Let’s check our understanding of match by guessing what each of the following expressions evaluates to, and why.

"abcd" match {
  case "bcde" => 0
  case "cdef" => 1
  case "abcd" => 2
}

1 match {
  case 0 => "zero"
  case 1 => "one"
  case 1 => "two"
}

1 match {
  case n => n + 1
  case 1 => 1000
}

1 match {
  case a => a
  case b => b + 1
  case c => c * 2
}

No Match

What happens if no pattern matches in a match expression? Take a guess, then write a match expression that fails to match and see if you managed to guess correctly. (At this point we have no reason to expect any particular behavior so any reasonable guess will do.)

2 match {
  case 0 => "zero"
  case 1 => "one"
}
// scala.MatchError: 2 (of class java.lang.Integer)
//  at repl.Session$App$$anonfun$5.apply(match.md:37)

7.3 The Natural Numbers

The natural numbers are the whole numbers, or integers, greater than or equal to zero. In other words the numbers 0, 1, 2, 3, … (Some people define the natural numbers as starting at 1, not 0. It doesn’t greatly matter for our purposes which definition you choose, but here we’ll assume they start at 0.)

One interesting property of the natural numbers is that we can define them recursively. That is, we can define them in terms of themselves. This kind of circular definition seems like it would lead to nonsense. We avoid this by including in the definition a base case that ends the recursion. Concretely, the definition is:

A natural number n is

• 0; or
• 1 + m, where m is a natural number.

The case for 0 is the base case, whilst the other case is recursive as it defines a natural number n in terms of a natural number m. Because m is always smaller than n, and the base case is the smallest possible natural number, this definition defines all of the natural numbers.

Given a natural number, say, 3, we can break it down using the definition above as follows:

3 = 1 + 2 = 1 + (1 + 1) = 1 + (1 + (1 + 0))

We use the recursive rule to expand the equation until we cannot use it any more. We then use the base case to stop the recursion.

7.4 Structural Recursion

Now onto structural recursion. The structural recursion pattern for the natural numbers gives us two things:

• a reusable code skeleton for processing any natural number; and
• the guarantee that we can use this skeleton to implement any computation on natural numbers.

Remember we wrote boxes as

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox.beside(boxes(n-1))
  }

When we developed boxes we just seemed to stumble upon this pattern. Here we see that this pattern follows directly from the definition of the natural numbers. Remember the recursive definition of the natural numbers: a natural number n is

• 0; or
• 1 + m, where m is a natural number.

The patterns in the match expression exactly match this definition. The expression

count match {
  case 0 => ???
  case n => ???
}

means we’re checking count for two cases, the case when count is 0, and the case when count is any other natural number n (which is 1 + m).

The right hand side of the match expression says what we do in each case. The case for zero is Image.empty. The case for n is aBox.beside(boxes(n-1)).

Now for the really important point. Notice that the structure of the right-hand side mirrors the structure of the natural number we match. When we match the base case 0, our result is the base case Image.empty. When we match the recursive case n the structure of the right hand side matches the structure of the recursive case in the definition of natural numbers. The definition states that n is 1 + m. On the right-hand side we replace 1 with aBox, we replace + with beside, and we recursively call boxes with m (which is n-1) where the definition recurses.

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox.beside(boxes(n-1))
  }

To reiterate, the left hand side of the match expression exactly matches the definition of natural numbers. The right-hand also matches the definition but we replace natural numbers with images. The image that is equivalent to zero is Image.empty. The image that is equivalent to 1 + m is aBox.beside(boxes(m)).

This general pattern holds for anything we care to write that transforms the natural numbers into some other type. We always have a match expression. We always have the two patterns, corresponding to the base and recursive cases. The right hand side expressions always consist of the base case, and the recursive case which itself has a result specific substitute for 1 and +, and a recursive call for n-1.

def name(count: Int): Result =
  count match {
    case 0 => resultBase
    case n => resultUnit add name(n-1)
  }

We’re now ready to go explore the fun that can be had with this simple but powerful tool.

Exercises

Three (or More) Stacks

We’ve seen how to create a horizontal row of boxes. Now write a method stacks that takes a natural number as input and creates a vertical stack of boxes.

def stacks(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox.above(boxes(n-1))
  }

Alternating Images

We do more with the counter than simply using it in the recursive call. In this exercise we’ll choose one Image when the counter is odd and a different Image when the counter is even. This will give us a row of alternating images as shown in fig. 23.

Figure 23: A row constructed by alternating between two different images.

To do this we need to learn about a new method on Int. The modulo method, written %, returns the remainder of dividing one Int by another. Here are some examples.

4 % 2
// res1: Int = 0
3 % 2
// res2: Int = 1
2 % 2
// res3: Int = 0
1 % 2
// res4: Int = 1

We can see that when the first number is even the result is 0; otherwise it is 1. So we need to check is the result is 0 and act accordingly. There are a few ways to do this. Here’s one example

(4 % 2 == 0) match {
  case true  => "It's even!"
  case false => "It's odd!"
}
// res5: String = "It's even!"

Here we match against the result of the comparison (4 % 2 == 0). The type of this expression is Boolean, which has two possible values (true and false).

For Booleans there is special syntax that is more compact than match: an if expression. Here’s the same code rewritten using if.

if(4 % 2 == 0) "It's even!"
else "It's odd!"
// res6: String = "It's even!"

Use whichever you are more comfortable with!

That’s all the background we need. Now we can write the method we’re interested in. Here’s the skeleton:

def alternatingRow(count: Int): Image =
  ???

Implement the method. It’s up to you what you choose for the two images used in the output.

val star = Image
  .star(5, 30, 15, 45.degrees)
  .strokeColor(Color.teal)
  .on(Image.star(5, 12, 7, 45.degrees).strokeColor(Color.royalBlue))
  .strokeWidth(5.0)

val circle = Image
  .circle(60)
  .strokeColor(Color.midnightBlue)
  .on(Image.circle(24).strokeColor(Color.plum))
  .strokeWidth(5.0)

def alternatingRow(count: Int): Image = {
  count match {
    case 0 => Image.empty
    case n =>
      if(n % 2 == 0) star.beside(alternatingRow(n-1))
      else circle.beside(alternatingRow(n-1))
  }
}

Getting Creative

We can use the counter to modify the image in other ways. For example we can make the color, size, or any othe property of an image depend on the counter. I have made an example in fig. 24, but come up with your own ideas. Implement a method

def funRow(count: Int): Image =
  ???

that generates such an image.

Figure 24: A row constructed by making size and color depend on the counter.

def funRow(count: Int): Image = {
  count match {
    case 0 => Image.empty
    case n =>
      Image
        .star(7, (10 * n), (7 * n), 45.degrees)
        .strokeColor(Color.azure.spin((5 * n).degrees))
        .strokeWidth(7.0)
        .beside(funRow(n - 1))
  }
}

Cross

Our final exercise is to create a method cross that will generate cross images. fig. 25 shows four cross images, which correspond to calling the method cross with 0 to 3.

The method skeleton is

def cross(count: Int): Image =
  ???

Figure 25: Crosses generated by count from 0 to 3.

People often find this exercise harder than the preceding ones, so we’ll make the process very explicit here.

Firstly, what pattern will we use to fill in the body of cross? Write out the pattern.

def cross(count: Int): Image =
  count match {
    case 0 => <resultBase>
    case n => <resultUnit> <add> cross(n-1)
  }

Now we’ve identified the pattern we’re using, we need to fill in the problem specific parts:

• the base case; and
• the unit and addition operators.

Hint: use fig. 25 to identify the elements above.

Now finish the implementation of cross.

def cross(count: Int): Image = {
    count match {
      case 0 =>
        Image.regularPolygon(6, 10, 0.degrees)
          .strokeColor(Color.deepSkyBlue.spin(-180.degrees))
          .strokeWidth(5.0)
      case n =>
        val circle = Image
          .circle(20)
          .strokeColor(Color.deepSkyBlue)
          .on(Image.circle(15).strokeColor(Color.deepSkyBlue.spin(-15.degrees)))
          .on(Image.circle(10).strokeColor(Color.deepSkyBlue.spin(-30.degrees)))
          .strokeWidth(5.0)
        circle.beside(circle.above(cross(n - 1)).above(circle)).beside(circle)
    }
  }

7.5 Reasoning about Recursion

We’re now experienced users of structural recursion over the natural numbers. Let’s now return to our substitution model and see if it works with our new tool of recursion.

Recall that substitution says we can substitute the value of an expression wherever we see a value. In the case of a method call, we can substitute the body of the method with appropriate renaming of the parameters.

Our very first example of recursion was boxes, written like so:

val aBox = Image.square(20).fillColor(Color.royalBlue)

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox.beside(boxes(n-1))
  }

Let’s try using substitution on boxes(3) to see what we get.

Our first substitution is

boxes(3)
// Substitute body of `boxes`
3 match {
  case 0 => Image.empty
  case n => aBox.beside(boxes(n-1))
}

Knowing how to evaluate a match expression and using substitution again gives us

3 match {
  case 0 => Image.empty
  case n => aBox.beside(boxes(n-1))
}
// Substitute right-hand side expression of `case n`
aBox.beside(boxes(2))

We can substitute again on boxes(2) to obtain

aBox.beside(boxes(2))
// Substitute body of boxes
aBox.beside {
  2 match {
    case 0 => Image.empty
    case n => aBox.beside(boxes(n-1))
  }
}
// Substitute right-hand side expression of `case n`
aBox.beside {
  aBox.beside(boxes(1))
}

Repeating the process a few more times we get

aBox.beside {
  aBox.beside {
    1 match {
      case 0 => Image.empty
      case n => aBox.beside(boxes(n-1))
    }
  }
}
// Substitute right-hand side expression of `case n`
aBox.beside {
  aBox.beside {
      aBox.beside(boxes(0))
  }
}
// Substitute body of boxes
aBox.beside {
  aBox.beside {
    aBox.beside {
      0 match {
        case 0 => Image.empty
        case n => aBox.beside(boxes(n-1))
      }
    }
  }
}
// Substitute right-hand side expression of `case 0`
aBox.beside {
  aBox.beside {
    aBox.beside {
      Image.empty
    }
  }
}

Our final result, which simplifies to

aBox.beside(aBox).beside(aBox).beside(Image.empty)

is exactly what we expect. Therefore we can say that substitution works to reason about recursion. This is great! However the substitutions are quite complex and difficult to keep track of without writing them down.

7.5.1 Reasoning About Structural Recursion

There is a more practical way to reason about structural recursion. Structural recursion guarantees the overall recursion is correct if we get the individual components correct. There are two parts to the structural recursion; the base case and the recursive case. The base case we can check just by looking at it. The recursive case has the recursive call (the method calling itself) but we don’t have to consider this. It is given to us by structural recursion so it will be correct so long as the other parts are correct. We can simply assume the recursive call it correct and then check that we are doing the right thing with the result of this call.

Let’s apply this to reasoning about boxes.

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox.beside(boxes(n-1))
  }

We can tell the base case is correct by inspection. Looking at the recursive case we assume that boxes(n-1) will do the right thing. The question then becomes: is what we do with the result of the recursive call boxes(n-1), correct? The answer is yes: if the recursion boxes(n-1) creates n-1 boxes in a line, sticking a box in front of them is the right thing to do. Since the individual cases are correct the whole thing is guaranted correct by structural recursion.

This way of reasoning is much more compact than using substitution and guaranteed to work if we’re using structural recursion.

Exercises

Below are some rather silly examples of structural recursion. Work out if the methods do what they claim to do without running them.

// Given a natural number, returns that number
// Examples:
//   identity(0) == 0
//   identity(3) == 3
def identity(n: Int): Int =
  n match {
    case 0 => 0
    case n => 1 + identity(n-1)
  }

// Given a natural number, double that number
// Examples:
//   double(0) == 0
//   double(3) == 6
def double(n: Int): Int =
  n match {
    case 0 => 0
    case n => 2 * double(n-1)
  }

def double(n: Int): Int =
  n match {
    case 0 => 0
    case 1 => 1
    case n => 2 * double(n-1)
  }

2(n-1 + 1) == 2(n-1) + 2

def double(n: Int): Int =
  n match {
    case 0 => 0
    case n => 2 + double(n-1)
  }

7.6 Conclusions

In this chapter we’ve seen our first big pattern for structuring code, structural recursion over the natural numbers. There are a few key points.

First is the structural recursion pattern itself. We saw we can use this to write methods that produce a value with a varying size, and the pattern is the same everytime. We’ve seen a lot of examples that generate images, but we can use this pattern for anything that is transforming a natural number into anything else (including other natural numbers). We’ll use this pattern, and other variants of structural recursion, throughout the book.

The second big idea is how we reason about structural recursion. We can use substitution but it is easier to take a shortcut. For structural recursion we are guaranteed to get the correct result if we get the base case and the recursive case correct. In particular we don’t need to reason through the recursive call; we assume it returns the correct result and only check that we correctly implement the next step adding to the result.

The third key point is that we can use the value of the counter to do other things beyond the recursion. We looked at using it to adjust the images we created at each step, which gives us new creative possibilities.

In the next section we’ll look at creating more complex images using structural recursion, and see a few new techniques we can use with it.

8 Fractals

A fractal is an image that is self-similar, meaning that it contains copies of itself. Fractals are an intriguing type of image as they build complex output from simple rules. In this chapter we will build some simple fractals, get more experience with structural recursion over natural numbers, and finally learn more programming techniques.

import doodle.core._
import doodle.image._
import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

8.1 The Chessboard

In this exercise and the next we’re trying to sharpen your eye for recursive structure.

Our first image is the chessboard. Though arguably not a fractal, the chessboard does contain itself: a 4x4 chessboard can be constructed from 4 2x2 chessboards, an 8x8 from 4 4x4s, and so on. The picture in fig. 26 shows this.

Figure 26: Chessboards generated by count from 0 to 2.

Your mission in this exercise is to identify the recursive structure in a chessboard, and implement a method to draw chessboards. The method skeleton is

def chessboard(count: Int): Image =
  ???

Implement chessboard. Remember we can use the structural recursion skeleton and reasoning technique to guide our implementation.

def chessboard(count: Int): Image =
  count match {
    case 0 => resultBase
    case n => resultUnit add chessboard(n-1)
  }

val blackSquare = Image.rectangle(30, 30).fillColor(Color.black)
val redSquare   = Image.rectangle(30, 30).fillColor(Color.red)

val base =
  (redSquare.beside(blackSquare)).above(blackSquare.beside(redSquare))

def chessboard(count: Int): Image = {
  val blackSquare = Image.rectangle(30, 30).fillColor(Color.black)
  val redSquare   = Image.rectangle(30, 30).fillColor(Color.red)

  val base =
    (redSquare.beside(blackSquare)).above(blackSquare.beside(redSquare))
  count match {
    case 0 => base
    case n =>
      val unit = chessboard(n-1)
      (unit.beside(unit)).above(unit.beside(unit))
  }
}

If you have prior programming experience you might have immediately thought of creating a chessboard via two nested loops. Here we’re taking a different approach by defining a larger chessboard as a composition of smaller chessboards. Grasping this different approach to decomposing problems is a key step in becoming proficient in functional programming.

8.2 Sierpinkski Triangle

The Sierpinski triangle, show in fig. ¿fig:fractals:sierpinski?, is a famous fractal. (Technically, fig. ¿fig:fractals:sierpinski? shows a Sierpinkski triangle.)

Figure 27: The Sierpinski triangle.

Although it looks complicated we can break the structure down into a form that we can generate with structural recursion over the natural numbers. Implement a method with skeleton

def sierpinski(count: Int): Image =
  ???

No hints this time. We’ve already seen everything we need to know.

def sierpinski(count: Int): Image = {
  val triangle = Image.triangle(10, 10).strokeColor(Color.magenta)
  count match {
    case 0 => triangle.above(triangle.beside(triangle))
    case n =>
      val unit = sierpinski(n-1)
      unit.above(unit.beside(unit))
  }
}

8.3 Auxiliary Parameters

We’ve seen how to use structural recursion over the natural numbers to write a number of interesting programs. In this section we’re going to learn how auxillary parameters allow us to write more complex programs. An auxiliary parameter is just an additional parameter to our method that allows us to pass extra information down the recursive call.

For example, imagine creating the picture in fig. 28, which shows a line of boxes that grow in size as we move along the line.

Figure 28: Boxes that grow in size with each recursion.

How can we create this image?

We know it has to be a structural recursion over the natural numbers, so we can immediately write down the skeleton

def growingBoxes(count: Int): Image =
  count match {
    case 0 => base
    case n => unit add growingBoxes(n-1)
  }

Using what we learned working with boxes earlier we can go a bit further and write down

def growingBoxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => Image.square(???).beside(growingBoxes(n-1))
  }

The challenge becomes how to make the box grow in size as we move to the right.

There are two ways to do this. The tricky way is to switch the order in the recursive case and make the size of the box a function of n. Here’s the code.

def growingBoxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => growingBoxes(n-1).beside(Image.square(n*10))
  }

Spend some time figuring out why this works before moving on to the solution using an auxiliary parameter.

Alternatively we can simply add another parameter to growingBoxes that tells us how big the current box should be. When we recurse we change this size. Here’s the code.

def growingBoxes(count: Int, size: Int): Image =
  count match {
    case 0 => Image.empty
    case n => 
      Image
        .square(size)
        .beside(growingBoxes(n-1, size + 10))
  }

The auxiliary parameter method has two advantages: we only have to think about what changes from one recursion to the next (in this case, the box gets larger), and it allows the caller to change this parameter (for example, making the starting box larger or smaller).

Now we’ve seen the auxiliary parameter method let’s practice using it.

Gradient Boxes

In this exercise we’re going to draw a picture like that in fig. 29. We already know how to draw a line of boxes. The challenge in this exercise is to make the color change at each step.

Hint: you can spin the fill color at each recursion.

Figure 29: Five boxes filled with changing colors starting from Royal Blue

def gradientBoxes(n: Int, color: Color): Image =
  n match {
    case 0 => Image.empty
    case n =>
      aBox
        .fillColor(color)
        .beside(gradientBoxes(n - 1, color.spin(15.degrees)))
  }

def gradientBoxes(n: Int): Image =
  n match {
    case 0 => Image.empty
    case n =>
      aBox
        .fillColor(Color.royalBlue.spin((15 * n).degrees))
        .beside(gradientBoxes(n - 1))
  }

Concentric Circles

Now let’s try a variation on the theme, drawing concentric circles as shown in fig. 30. Here we are changing the size rather than the color of the image at each step. Otherwise the pattern stays the same. Have a go at implementing it.

Figure 30: Concentric circles, colored Royal Blue

def concentricCircles(count: Int, size: Int): Image =
  count match {
    case 0 => Image.empty
    case n => 
      Image
        .circle(size)
        .on(concentricCircles(n-1, size + 5))
  }

Once More, With Feeling

Now let’s combine both techniques to change size and color on each step, giving results like those shown in fig. 31. Experiment until you find something you like.

Figure 31: Concentric circles with interesting color variations

def circle(size: Int, color: Color): Image =
  Image.circle(size).strokeWidth(3.0).strokeColor(color)

def fadeCircles(n: Int, size: Int, color: Color): Image =
  n match {
    case 0 => Image.empty
    case n => 
      circle(size, color)
        .on(fadeCircles(n-1, size+7, color.fadeOutBy(0.05.normalized)))
  }

def gradientCircles(n: Int, size: Int, color: Color): Image =
  n match {
    case 0 => Image.empty
    case n => 
      circle(size, color)
        .on(gradientCircles(n-1, size+7, color.spin(15.degrees)))
  }

def image: Image =
  fadeCircles(20, 50, Color.red)
    .beside(gradientCircles(20, 50, Color.royalBlue))

8.4 Nested Methods

A method is a declaration. The body of a method can contain declarations and expressions. Therefore, a method declaration can contain other method declarations.

To see why this is useful, lets look at a method we wrote earlier:

def cross(count: Int): Image = {
  val unit = Image.circle(20)
  count match {
    case 0 => unit
    case n => unit.beside(unit.above(cross(n-1)).above(unit)).beside(unit)
  }
}

We have declared unit inside the method cross. This means the declaration of unit is only in scope within the body of cross. It is good practice to limit the scope of declarations to the minimum needed, to avoid accidentally shadowing other declarations. However, let’s consider the runtime behavior of cross and we’ll see that is has some undesirable characteristics.

We’ll use our substitution model to expand cross(1).

cross(1)
// Expands to
{
  val unit = Image.circle(20)
  1 match {
    case 0 => unit
    case n => unit.beside(unit.above(cross(n-1)).above(unit)).beside(unit)
  }
}
// Expands to
{
  val unit = Image.circle(20)
  unit.beside(unit.above(cross(0)).above(unit)).beside(unit)
}
// Expands to
{
  val unit = Image.circle(20)
  unit.beside(unit.above
  {
    val unit = Image.circle(20)
    0 match {
      case 0 => unit
      case n => unit.beside(unit.above(cross(n-1)).above(unit)).beside(unit)
    }
  }
  .above(unit)).beside(unit)
}
// Expands to
{
  val unit = Image.circle(20)
  unit.beside(unit.above
  {
    val unit = Image.circle(20)
    unit
  }
  .above(unit)).beside(unit)
}

The point of this enormous expansion is to demonstrate that we’re recreating unit every time we recurse within cross. We can prove this is true by printing something every time unit is created.

def cross(count: Int): Image = {
  val unit = {
    println("Creating unit")
    Image.circle(20)
  }
  count match {
    case 0 => unit
    case n => unit.beside(unit.above(cross(n-1)).above(unit)).beside(unit)
  }
}

cross(1)
// Creating unit
// Creating unit
// res1: Image = Beside(
//   Beside(Circle(20.0), Above(Above(Circle(20.0), Circle(20.0)), Circle(20.0))),
//   Circle(20.0)
// )

This doesn’t matter greatly for unit because it’s very small, but we could be doing something that takes up a lot of memory or time, and it’s undesirable to repeat it when we don’t have to.

We could solve this by shifting unit outside of cross.

val unit = {
  println("Creating unit")
  Image.circle(20)
}
// Creating unit
// unit: Image = Circle(20.0)

def cross(count: Int): Image = {
  count match {
    case 0 => unit
    case n => unit beside (unit above cross(n-1) above unit) beside unit
  }
}

cross(1)
// res3: Image = Beside(
//   Beside(Circle(20.0), Above(Above(Circle(20.0), Circle(20.0)), Circle(20.0))),
//   Circle(20.0)
// )

This is undesirable because unit now has a larger scope than needed. A better solution it to use a nested or internal method.

def cross(count: Int): Image = {
  val unit = {
    println("Creating unit")
    Image.circle(20)
  }
  def loop(count: Int): Image = {
    count match {
      case 0 => unit
      case n => unit beside (unit above loop(n-1) above unit) beside unit
    }
  }

  loop(count)
}

cross(1)
// Creating unit
// res5: Image = Beside(
//   Beside(Circle(20.0), Above(Above(Circle(20.0), Circle(20.0)), Circle(20.0))),
//   Circle(20.0)
// )

This has the behavior we’re after, creating unit only once while minimising its scope. The internal method loop is using structural recursion exactly as before. We just need to ensure that we call it in cross. I usually name this sort of internal method loop or iter (short for iterate) to indicate that they’re performing a loop.

This technique is just a small variation of what we’ve done already, but let’s do a few exercises to make sure we’ve got the pattern.

Exercises

Chessboard

Rewrite chessboard using a nested method so that blackSquare, redSquare, and base are only created once when chessboard is called.

def chessboard(count: Int): Image = {
  val blackSquare = Image.square(30) fillColor Color.black
  val redSquare   = Image.square(30) fillColor Color.red

  val base =
    (redSquare   beside blackSquare) above (blackSquare beside redSquare)
  count match {
    case 0 => base
    case n =>
      val unit = cross(n-1)
      (unit beside unit) above (unit beside unit)
  }
}

def chessboard(count: Int): Image = {
  val blackSquare = Image.square(30) fillColor Color.black
  val redSquare   = Image.square(30) fillColor Color.red
  val base =
    (redSquare   beside blackSquare) above (blackSquare beside redSquare)
  def loop(count: Int): Image =
    count match {
      case 0 => base
      case n =>
        val unit = loop(n-1)
        (unit beside unit) above (unit beside unit)
    }

  loop(count)
}

Boxing Clever

Rewrite boxes, shown below, so that aBox is only in scope within boxes and only created once when boxes is called.

val aBox = Image.square(20).fillColor(Color.royalBlue)

def boxes(count: Int): Image =
  count match {
    case 0 => Image.empty
    case n => aBox.beside(boxes(n-1))
  }

def boxes(count: Int): Image = {
  val aBox = Image.square(20).fillColor(Color.royalBlue)
  count match {
    case 0 => Image.empty
    case n => aBox beside boxes(n-1)
  }
}

def boxes(count: Int): Image = {
  val aBox = Image.square(20).fillColor(Color.royalBlue)
  def loop(count: Int): Image =
    count match {
      case 0 => Image.empty
      case n => aBox beside loop(n-1)
    }

  loop(count)
}

8.5 Exercises

We now have a number of new tools in our toolbox. It’s time to get some practice putting them all together.

Here’s an example of the familiar chessboard pattern. We have used an auxillary parameter to pass along a color that we change at each recursion. By changing the hue by a prime number we end up a complex pattern with infrequently repeating colors. See fig. 32 for an example.

def chessboard(count: Int, color: Color): Image =
  count match {
    case 0 =>
      val contrast = color.spin(180.degrees)
      val box = Image.square(20)
      box
        .fillColor(color)
        .beside(box.fillColor(contrast))
        .above(box.fillColor(contrast).beside(box.fillColor(color)))

    case n =>
      chessboard(n - 1, color.spin(17.degrees))
        .beside(chessboard(n - 1, color.spin(-7.degrees)))
        .above(
          chessboard(n - 1, color.spin(-19.degrees))
            .beside(chessboard(n - 1, color.spin(3.degrees)))
        )
  }

Figure 32: Chessboard with colors evolving at each recursive step.

Your mission is to take the ideas we’ve seen in this chapter, perhaps using the chessboard example for inspiration, and create your own artwork. No other guidelines this time; it’s up to you and your imagination.

9 Horticulture and Higher-order Functions

In this chapter we’re going to learn how to draw flowers and to use functions as first-class values.

We know that programs work with values, but not all values are first-class. A first-class value is something we can pass as a parameter to a method, or return as a result from a method call, or give a name using val.

If we pass a function as an argument to another function then:

• the function that is passed is being used as a first-class value; and
• the function that is receiving the function parameter is called a higher-order function.

This terminology is not especially important, but you’ll encounter it in other writing so it’s useful to know (at least vaguely) what it means. It will soon become clearer when we see some examples.

So far we have used the terms function and method interchangeably. We’ll soon see that in Scala these two terms have distinct, though related, meanings.

Enough background. Let’s dive in to see:

• how we create functions in Scala; and
• how we use first-class functions to structure programs.

Our motivating example for this will be drawing flowers as in fig. 33.

Figure 33: A flower created using the techniques in this chapter

import doodle.core._
import doodle.image._
import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

9.1 Functions

A function is basically a method, but we can use a function as a first-class value:

• we can pass it as an argument or parameter to a method or function;
• we can return it from a method or function; and
• we can give it a name using val.

Here’s an example where we give the name add42 to a function that adds 42 to its input.

val add42 = (x: Int) => x + 42
// add42: Int => Int = <function1>

We can call it just like we’d call a method.

add42(0)
// res0: Int = 42

This is an example of a function literal. Let’s learn about them now.

9.1.1 Function Literals

We’ve just seen an example of a function literal, which was

(x: Int) => x + 42
// res1: Int => Int = <function1>

The general syntax is an extension of this.

(parameter: type, ...) => expression

9.1.2 Function Types

To pass functions to methods we need to know how to write down their types (because when we declare a parameter we have to declare its type).

We write a function type like (A, B) => C where A and B are the types of the parameters and C is the result type. The same pattern generalises from functions of no arguments to an arbitrary number of arguments.

Here’s an example. We create a method that accepts a function, and that function is from Int to Int. We write this type as Int => Int or (Int) => Int.

def squareF(x: Int, f: Int => Int): Int =
  f(x) * f(x)

We can pass add42 to this method

squareF(0, add42)
// res2: Int = 1764

We could also pass a function literal

squareF(0, x => x + 42)
// res3: Int = 1764

Note that we didn’t have to put the parameter type on the function literal in this case because Scala has enough information to infer the type.

(A, B, ...) => C

A => B

9.1.3 Functions as Objects

All first class values are objects in Scala, including functions. This means functions can have methods, including some useful means for composition.

val addTen = (a: Int) => a + 10
// addTen: Int => Int = <function1>
val double = (a: Int) => a * 2
// double: Int => Int = <function1>
val combined = addTen.andThen(double) // this composes the two functions
// combined: Int => Int = scala.Function1$$Lambda$9669/1403896095@119ecd3a // this composes the two functions
combined(5)
// res4: Int = 30

Calling a function is actually calling the method called apply on the function. Scala allows a shortcut for any object that has a method called apply, where can drop the method name apply and write the call like a function call. This means the following are equivalent.

val halve = (a: Int) => a / 2
// halve: Int => Int = <function1>
halve(4)
// res5: Int = 2
halve.apply(4)
// res6: Int = 2

9.1.4 Converting Methods to Functions

Methods are very similar to functions, so Scala provides a way to convert functions to methods. If we follow a method name with a _ it will be converted to a function.

def times42(x: Int): Int =
  x * 42

val times42Function = times42 _
// times42Function: Int => Int = <function1>

We can also write a method call but replace all parameters with _ and Scala will convert the method to a function.

val times42Function2 = times42(_)
// times42Function2: Int => Int = <function1>

Exercises

9.1.4.0.1 Function Literals

Let’s get some practice writing function literals. Write a function literal that:

• squares it’s Int input;
• has a Color parameter and spins the hue of that Color by 15 degrees; and
• takes an Image input and creates four copies in a row, where each copy is rotated by 90 degrees relative to the previous image (use the rotate method on Image to achieve this.)

(x: Int) => x * x
// res7: Int => Int = <function1>

(c: Color) => c.spin(15.degrees)
// res8: Color => Color.HSLA = <function1>

(image: Image) => 
  image.beside(image.rotate(90.degrees))
    .beside(image.rotate(180.degrees))
    .beside(image.rotate(270.degrees))
    .beside(image.rotate(360.degrees))
// res9: Image => Image = <function1>

Function Types

Here’s an interesting function we’ll do more with in later sections. We don’t need to understand what it does right now, though you might want to experiment with it.

val roseFn = (angle: Angle) =>
  Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)

What is the type of the function roseFn defined above? What does this type mean?

9.2 Parametric Curves

Right now we only know how to create basic shapes like circles and rectangles. We’ll need more control to create the flower shapes that are our goal. We’re going to use a tool from mathematics known as a parametric equation or parametric curve to do so.

A parametric equation is a function from some input (the parameter in “parametric”) to a point, a location in space. The input tells us how far along the curve we are. For example, a parametric equation for a circle might have as its input an angle and it would give us the point on the circle at that angle. In Scala we could write

def parametricCircle(angle: Angle): Point =
  ???

If we choose lots of different values for the input, and then draw a shape at each point we get back from the parametric equation, we can suggest the shape of the curve.

In fig. 34 we give an example of drawing small circles at the points generated by the parametric equation for a circle. Going from left to right we draw points every 90, 45, and 22.5 degrees. You can see how the outline of the shape, the large circle, becomes clearer as we draw more points.

Figure 34: Parametric circle with points drawn, from left to right, every 90, 45, and 22.5 degrees.

To create parametric curves we need to learn 1) how to represent points in Doodle, 2) how to position an image at a particular point in space, and 3) revise a bit of geometry you might not have touched since high school. Let’s look at each item in turn.

9.3 Points

In Doodle we have a Point type to represent a position in two dimensions. We have two equivalent representations in terms of:

• x and y coordinates, called a cartesian representation; and
• in terms of an angle and distance (the radius) at that angle from the origin, called a polar representation.

This difference is shown in fig. 35.

Figure 35: A point represented in cartesian (x and y) coordinates and polar (radius and angle) coordinates

We can create points in the cartesian representation using Point(Double, Double) where the two parameters are the x and y coordinates, and in the polar representation using Point(Double, Angle) where we specify the radius and the angle. The table below shows the main methods on Point.

9.4 Flexible Layout

Can we position an Image at a point? So far we only know how to layout images with on, beside, and above. We need an additional tool, the at method, to achieve more flexible layout. Here’s an example using at that draws a dot at the corners of a square.

val dot = Image.circle(5).strokeWidth(3).strokeColor(Color.crimson)
val squareDots =
  dot.at(0, 0)
    .on(dot.at(0, 100))
    .on(dot.at(100, 100))
    .on(dot.at(100, 0))

This produces the image shown in fig. 36.

Figure 36: Using at layout to position four dots at the corners of a square.

To understand how at layout works, and why we have to place the dots on each other, we need to know a bit more about how Doodle does layout.

Every Image in Doodle has a point called its origin, and a bounding box which determines the limits of the image. By convention the origin is in the center of the bounding box but this is not required. We can see the origin and bounding box of an Image by calling the debug method. In fig. 37 we show the output of the code

val c = Image.circle(40)
val c1 = c.beside(c.at(10, 10)).beside(c.at(10, -10)).debug
val c2 = c.debug.beside(c.at(10, 10).debug).beside(c.at(10, -10).debug)
val c3 = c.debug.beside(c.debug.at(10, 10)).beside(c.debug.at(10, -10))
c1.above(c2).above(c3)

This shows how the origin and bounding box change as we combines Images.

Figure 37: Using the debug method to inspect the origin and bounding box of an Image

When we layout Images using above, beside, or on it is the bounding boxes and origins that determine how the individual components are positioned relative to one another. For on the rule is that the origins are placed on top of one another. For beside the rule is that origins are horizontally aligned and placed so that the bounding boxes just touch. The origin of the compound image is placed equidistant from the left and right edges of the compound bounding box on the horizontal line that connects the origins of the component images. The rule for above is the same as beside, but we use vertical alignment instead of horizontal alignment.

Using at we can move an Image relative to its origin. In the examples we’re using here we want all the elements to share the same origin, so we use on to combine Images that we have moved using at.

There are four ways we can call at:

• by passing the x- and y-offset, as in dot.at(100, 100);
• by passing the radius and angle, as in dot.at(100, 90.degrees);
• by passing a Point, as in dot.at(Point(100, 100)); or
• by passing a Vec (a vector) giving the offset, as in dot.at(Vec(100, 100)).

We can convert a Point to a Vec using the toVec method.

Point.cartesian(1.0, 1.0).toVec
// res1: Vec = Vec(1.0, 1.0)

9.5 Geometry

The final building block is the geometry to position points. If a point is positioned at a distance r from the origin at an angle a, the x- and y-coordinates are (a.cos) * r and (a.sin) * r respectively. Alternatively we can just use polar form! For example, here’s how we would position a point at a distance of 1 and an angle of 45 degrees.

val polar = Point(1.0, 45.degrees)
// polar: Point = Polar(1.0, Angle(0.7853981633974483))
val cartesian = Point((45.degrees.cos) * 1.0, (45.degrees.sin) * 1.0)
// cartesian: Point = Cartesian(0.7071067811865476, 0.7071067811865475)

// They are the same
polar.toCartesian == cartesian
// res2: Boolean = true
cartesian.toPolar == polar
// res3: Boolean = true

9.6 Putting It All Together

We can put this all together to create a parametric circle. In cartesian coordinates the code for a parametric circle with radius 200 is

def parametricCircle(angle: Angle): Point =
  Point.cartesian(angle.cos * 200, angle.sin * 200)

In polar form it is simply

def parametricCircle(angle: Angle): Point =
  Point.polar(200, angle)

Now we could sample a number of points evenly spaced around the circle. To create an image we can draw something at each point (say, a triangle).

def sample(samples: Int): Image = {
  // Angle.one is one complete turn. I.e. 360 degrees
  val step = Angle.one / samples
  val dot = Image
              .triangle(10, 10)
              .fillColor(Color.limeGreen)
              .strokeColor(Color.lawngreen)
  def loop(count: Int): Image = {
    val angle = step * count
    count match {
      case 0 => Image.empty
      case n =>
        dot.at(parametricCircle(angle)).on(loop(n - 1))
    }
  }
  
  loop(samples)
}

This is a structural recursion, which is hopefully a familiar pattern by now.

If we draw this we’ll see the outline of a circle suggested by the triangles. See fig. 38, which shows the result of sample(72).

Figure 38: Triangles arranged in a circle, using the code from sample above.

9.6.1 Parametric Curves as First-class Functions

So far we haven’t seen anything that requires we use our parametric curves as functions instead of methods (and, indeed, we have defined them as method though we know we can easily convert methods to functions.) It’s time we got something useful from functions. Remember that functions are first-class values, which means: we can pass them to a method, we can return them from a method, and we can give them a name using val. We’re going to see an example where the first property—the ability to pass them as parameters—is useful.

We’ve just defined a method called sample that samples from our parametric curve. Right now it is restricted to sampling from the method parametricCircle. It would make a lot of sense to reuse this method with different parametric curves, which means we need to be able to pass a parametric curve to sample from to the sample method. We can do this with a function parameter. Here is what the code might look like.

def sample(samples: Int, dot: Image, curve: Angle => Point): Image = {
  val step = Angle.one / samples
  def loop(count: Int): Image = {
    val angle = step * count
    count match {
      case 0 => Image.empty
      case n =>
        dot.at(curve(angle)).on(loop(n - 1))
    }
  }
  
  loop(samples)
}

In this implementation of sample I have added two new parameters, the parametric curve to sample from and the Image to use to draw the samples. This gives us more flexibility in the output. Now we just need to define some more parametric curves, which is what the next exercise involves.

Exercises

We have some new tools in our toolbox. It’s time to have some fun exploring what we can do with them.

9.6.1.0.1 Spirals

To create a circle we keep the radius constant as the angle increases. If, instead, the radius increases as the angle increases we’ll get a spiral. (How quickly should the radius increase? It’s up to you! Different choices will give you different spirals.)

Implement a function or method parametricSpiral that creates a spiral.

def parametricSpiral(angle: Angle): Point =
  Point((Math.exp(angle.toTurns) - 1) * 200, angle)

9.6.1.0.2 Samples

Use the parametric curves we have defined so far to create something interesting. There is an example in fig. 39

Figure 39: A picture created using the parametric curves we have seen so far.

9.7 Flowers and Other Curves

In the previous section we saw that is was useful for methods to accept functions as parameters. In this section we’ll see that it is useful for methods to return functions.

We’ve seen all the basic steps we need to make our flowers. Now we just need to know the curve that makes the flower shape! The shape I used is known as the rose curve. One example is shown in fig. 40.

Figure 40: An example of the rose curve.

The code for the parametric curve that gives this shape is below.

// Parametric equation for rose with k = 7
val rose7 = (angle: Angle) =>
  Point((angle * 7).cos * 200, angle)

You may wonder why I called this function rose7. It’s because we can vary the shape by changing the value 7 to something else. We could make a method or function to which we pass the value of this parameter and this function would return a particular rose curve. Here’s that idea in code.

def rose(k: Int): Angle => Point =
  (angle: Angle) => Point((angle * k).cos * 200, angle)

The rose method describes a family of curves. They all look similar, and we create individuals by choosing a particular value for the parameter k. In fig. 41 we show more rose curves, this time with k as 5, 8, and 9 respectively.

Figure 41: Examples of rose curves, with the parameter k chosen as 5, 8, or 9.

Let’s look at some other interesting curves. In fig. 42 we show examples of a family of curves called Lissajous curves.

Figure 42: Examples of Lissajous curves, with the parameters a and b chosen as 1, 2, or 3.

The code for this is

def lissajous(a: Int, b: Int, offset: Angle): Angle => Point =
  (angle: Angle) =>
    Point(100 * ((angle * a) + offset).sin, 100 * (angle * b).sin)

The examples in fig. 42 use values of a and b of 1, 2, or 3, and the offset set to 90 degrees.

There are an unlimited number of functions we could use to create interesting curves. Let’s see one more example, this time of what known as an epicycloid. An epicycloid is produced when we trace a point on a circle rotating around another circle. We can stack circles on top of circles, and change the speed at which they rotate, to produce many different curves. For our example we are going to fix the number and radius of the circles and allow their speed of rotation to vary. Here is the code:

def epicycloid(a: Int, b: Int, c: Int): Angle => Point =
  (angle: Angle) =>
    (Point(75, angle * a).toVec + Point(32, angle * b).toVec + Point(15, angle * c).toVec).toPoint

You might notice this code converts points to vectors and back again. This is a little technical detail (we cannot add points but we can add vectors) that isn’t important if you aren’t familiar with vectors.

In fig. 43 we see three examples created by choosing the parameters a, b, c, as (1, 6, 14), (7, 13, 25), and (1, 7, -21) respectively.

Figure 43: Examples of epicycloid curves, with the parameters chosen as (1, 6, 14), (7, 13, 25), and (1, 7 -21).

Exercise

We now have a lot of tools to play with. Your task here is simply to use some of the ideas we’ve just seen to make an image that you like. For inspiration you could use the image that we started the chapter with, but don’t let it constrain you if you think of something else to explore.

9.8 Higher Order Methods and Functions

In previous sections we have seen the utility of passing functions to methods and returning functions from methods. In this section we’ll see the usefulness of *function composition**. Composition, in the mathematical rather than artistic sense, means creating something more complex by combining simpler parts. We could say we compose the numbers 1 and 1, using addition, to produce 2. By composing functions we mean to create a function that connects the output of one component function to the input of another component function.

Here’s an example. We use the andThen method to create a function that connects the output of the first function to the input of the second function.

val dropShadow = (image: Image) =>
  image.on(image.strokeColor(Color.black).fillColor(Color.black).at(5, -5))

val mirrored = (image: Image) =>
  image.beside(image.transform(Transform.horizontalReflection))

val composed = mirrored.andThen(dropShadow)

In fig. 44 we see the output of the program

val star = Image
  .star(100, 50, 5, 0.degrees)
  .fillColor(Color.fireBrick)
  .strokeColor(Color.dodgerBlue)
  .strokeWidth(7.0)
dropShadow(star)
  .beside(mirrored(star))
  .beside(composed(star))

This shows how the composed function applies the output of the first function to the second function: we first mirror the function then add a drop shadow.

Figure 44: Illustrating function composition by showing the output of the individual components and the composition.

Let’s see how we can apply function composition to our examples of parametric curves. One limitation of the parametric cures we’ve created so far is that their size is fixed. For example when we defined parametricCircle we fixed the radius at 200.

def parametricCircle(angle: Angle): Point =
  Point.polar(200, angle)

What if we want to create circles of different radius? We could use a method that returns a function like so.

def parametricCircle(radius: Double): Angle => Point = 
  (angle: Angle) => Point.polar(radius, angle)

This would be a reasonable solution but we’re going to explore a different approach using our new tool of function composition. Our approach will be this:

• each parametric curve will be of some default size that we’ll loosely define as “usually between 0 and 1”; and

• we’ll define a function scale that will change the size as appropriate.

A quick example will make this more concrete. Let’s redefine parametricCircle so the radius is 1.

val parametricCircle: Angle => Point = 
  (angle: Angle) => Point(1.0, angle)

Now we can define scale.

def scale(factor: Double): Point => Point =
  (point: Point) => Point(point.r * factor, point.angle)

We can use function composition to create circles of different sizes as follows.

val circle100 = parametricCircle.andThen(scale(100))
val circle200 = parametricCircle.andThen(scale(200))
val circle300 = parametricCircle.andThen(scale(300))

We can use the same approach for our spiral, adjusting the function slightly so the radius of the spiral varies from about 0.36 at 0 degrees to 1 at 360 degrees.

val parametricSpiral: Angle => Point =
  (angle: Angle) => Point(Math.exp(angle.toTurns - 1), angle)

Then we can compose with scale to produce spirals of different size.

val spiral100 = parametricSpiral.andThen(scale(100))
val spiral200 = parametricSpiral.andThen(scale(200))
val spiral300 = parametricSpiral.andThen(scale(300))

What else can we do with function composition?

Our parametric functions have type Angle => Point. We can compose these with functions of type Point => Image and with this setup we can make the “dots” from which we build our images depend on the point.

Here’s an example when the dots get bigger as the angle increases.

val growingDot: Point => Image = 
  (pt: Point) => Image.circle(pt.angle.toTurns * 20).at(pt)
  
val growingCircle = parametricCircle
  .andThen(scale(100))
  .andThen(growingDot)

Exercise: Sample

If we want to draw this function we’ll need to change sample so the parametric has type Angle => Image instead of Angle => Point. In other words we want the following skeleton.

def sample(samples: Int, curve: Angle => Image): Image =
  ???

Implement sample.

def sample(samples: Int, curve: Angle => Image): Image = {
  val step = Angle.one / samples
  def loop(count: Int): Image = {
    val angle = step * count
    count match {
      case 0 => Image.empty
      case n =>
        curve(angle).on(loop(n - 1))
    }
  }
  
  loop(samples)
}

Once we’ve implemented sample we can start drawing pictures. For example, in fig. 45 we have the output of growingCircle above.

Figure 45: A circle created by composing smaller components.

9.8.1 More Uses of Composition

At this point we can do a lot. Let’s see another example. Remember the concentric circles exercise we used as an example:

def concentricCircles(count: Int, size: Int): Image =
  count match {
    case 0 => Image.empty
    case n => Image.circle(size).on(concentricCircles(n-1, size + 5))
  }

This pattern allows us to create many different images by changing the use of Image.circle to another shape. However, each time we provide a new replacement for Image.circle, we also need a new definition of concentricCircles to go with it.

We can make concentricCircles completely general by supplying the replacement for Image.circle as a parameter. Here we’ve renamed the method to concentricShapes, as we’re no longer restricted to drawing circles, and made singleShape responsible for drawing an appropriately sized shape.

def concentricShapes(count: Int, singleShape: Int => Image): Image =
  count match {
    case 0 => Image.empty
    case n => singleShape(n).on(concentricShapes(n-1, singleShape))
  }

Now we can re-use the same definition of concentricShapes to produce plain circles, squares of different hue, circles with different opacity, and so on. All we have to do is pass in a suitable definition of singleShape:

// Passing a function literal directly:
val blackCircles: Image =
  concentricShapes(10, (n: Int) => Image.circle(50 + 5*n))

// Converting a method to a function:
def redCircle(n: Int): Image =
  Image.circle(50 + 5*n).strokeColor(Color.red)

val redCircles: Image =
  concentricShapes(10, redCircle _)

Exercises

The Colour and the Shape

Starting with the code below we are going to write color and shape functions to produce the image shown in fig. 46.

Figure 46: Colors and Shapes

def concentricShapes(count: Int, singleShape: Int => Image): Image =
  count match {
    case 0 => Image.empty
    case n => singleShape(n).on(concentricShapes(n-1, singleShape))
  }

The concentricShapes method is equivalent to the concentricCircles method from previous exercises. The main difference is that we pass in the definition of singleShape as a parameter.

Let’s think about the problem a little. We need to do two things:

1. write an appropriate definition of singleShape for each of the three shapes in the target image; and

2. call concentricShapes three times, passing in the appropriate definition of singleShape each time and putting the results beside one another.

Let’s look at the definition of the singleShape parameter in more detail. The type of the parameter is Int => Image, which means a function that accepts an Int parameter and returns an Image. We can declare a method of this type as follows:

def outlinedCircle(n: Int): Image =
  Image.circle(n * 10)

We can convert this method to a function, and pass it to concentricShapes to create an image of concentric black outlined circles:

concentricShapes(10, outlinedCircle _)

This produces the output shown in fig. 47.

Figure 47: Many outlined circles

The rest of the exercise is just a matter of copying, renaming, and customising this function to produce the desired combinations of colours and shapes:

def circleOrSquare(n: Int) =
  if(n % 2 == 0) Image.rectangle(n*20, n*20) else Image.circle(n*10)

concentricShapes(10, outlinedCircle).beside(concentricShapes(10, circleOrSquare))

See fig. 48 for the output.

Figure 48: Many outlined circles beside many circles and squares

For extra credit, when you’ve written your code to create the sample shapes above, refactor it so you have two sets of base functions—one to produce colours and one to produce shapes. Combine these functions using a combinator as follows, and use the result of the combinator as an argument to concentricShapes

def colored(shape: Int => Image, color: Int => Color): Int => Image =
  (n: Int) => ???

def concentricShapes(count: Int, singleShape: Int => Image): Image =
  count match {
    case 0 => Image.empty
    case n => singleShape(n).on(concentricShapes(n-1, singleShape))
  }

def rainbowCircle(n: Int) = {
  val color = Color.blue.desaturate(0.5.normalized).spin((n * 30).degrees)
  val shape = Image.circle(50 + n*12)
  shape.strokeWidth(10).strokeColor(color)
}

def fadingTriangle(n: Int) = {
  val color = Color.blue.fadeOut((1 - n / 20.0).normalized)
  val shape = Image.triangle(100 + n*24, 100 + n*24)
  shape.strokeWidth(10).strokeColor(color)
}

def rainbowSquare(n: Int) = {
  val color = Color.blue.desaturate(0.5.normalized).spin((n * 30).degrees)
  val shape = Image.rectangle(100 + n*24, 100 + n*24)
  shape.strokeWidth(10).strokeColor(color)
}

val answer =
  concentricShapes(10, rainbowCircle)
    .beside(
      concentricShapes(10, fadingTriangle)
        .beside(concentricShapes(10, rainbowSquare))
    )

def concentricShapes(count: Int, singleShape: Int => Image): Image =
  count match {
    case 0 => Image.empty
    case n => singleShape(n) on concentricShapes(n-1, singleShape)
  }

def colored(shape: Int => Image, color: Int => Color): Int => Image =
  (n: Int) =>
    shape(n).strokeWidth(10).strokeColor(color(n))

def fading(n: Int): Color =
  Color.blue.fadeOut((1 - n / 20.0).normalized)

def spinning(n: Int): Color =
  Color.blue.desaturate(0.5.normalized).spin((n * 30).degrees)

def size(n: Int): Double =
  100 + 24 * n

def circle(n: Int): Image =
  Image.circle(size(n))

def square(n: Int): Image =
  Image.square(size(n))

def triangle(n: Int): Image =
  Image.triangle(size(n), size(n))

val answer =
  concentricShapes(10, colored(circle, spinning))
    .beside(
      concentricShapes(10, colored(triangle, fading))
        .beside(concentricShapes(10, colored(square, spinning)))
    )
// answer: Image = Beside(
//   On(
//     StrokeColor(
//       StrokeWidth(Circle(340.0), 10.0),
//       HSLA(
//         Angle(9.42477796076938),
//         Normalized(0.5),
//         Normalized(0.5),
//         Normalized(1.0)
//       )
//     ),
//     On(
//       StrokeColor(
//         StrokeWidth(Circle(316.0), 10.0),
//         HSLA(
//           Angle(8.901179185171081),
//           Normalized(0.5),
//           Normalized(0.5),
//           Normalized(1.0)
//         )
//       ),
//       On(
//         StrokeColor(
//           StrokeWidth(Circle(292.0), 10.0),
//           HSLA(
//             Angle(8.377580409572781),
//             Normalized(0.5),
//             Normalized(0.5),
//             Normalized(1.0)
//           )
//         ),
//         On(
//           StrokeColor(
//             StrokeWidth(Circle(268.0), 10.0),
//             HSLA(
//               Angle(7.853981633974483),
//               Normalized(0.5),
//               Normalized(0.5),
//               Normalized(1.0)
//             )
//           ),
//           On(
//             StrokeColor(
//               StrokeWidth(Circle(244.0), 10.0),
//               HSLA(
//                 Angle(7.330382858376184),
//                 Normalized(0.5),
//                 Normalized(0.5),
//                 Normalized(1.0)
// ...

More Shapes

The concentricShapes methods takes an Int => Image function, and we can construct such as function using sample, the parametric curves we created earlier, and the various utilities we have created along the way. There is an example is fig. 49.

Figure 49: Concentric dotty circles

The code to create this is below.

def dottyCircle(n: Int): Image =
  sample(
    72,
    parametricCircle.andThen(scale(100 + n * 24)).andThen(growingDot)
  )

concentricShapes(10, colored(dottyCircle, spinning))

Use the techniques we’ve seen so far to create a picture of your choosing (perhaps similar to the flower with which we started the chapter). No solution here—there is no right or wrong answer.

9.9 Exercises

Now we are chock full of knowledge about functions, we’re going to return to the problem of drawing flowers. We’ll be asking you to do more design work here than we have done previously.

Your task is to break down the task of drawing a flower into small functions that work together. Try to give yourself as much creative freedom as possible, by breaking out each individual component of the task into a function.

Try to do this now. If you run into problems look at our decomposition below.

9.9.1 Components

We’ve identified two components of drawing flowers:

• the parametric equation; and
• the structural recursion over angles.

What other components might we abstract into functions? What are their types? (This is a deliberately open ended question. Explore!)

def scale(factor: Double): Point => Point = 
  (pt: Point) => {
    Point.polar(pt.r * factor, pt.angle)
  }

def sample(start: Angle, samples: Int, location: Angle => Point): Image = {
  // Angle.one is one complete turn. I.e. 360 degrees
  val step = Angle.one / samples
  val dot = Image.triangle(10, 10)
  def loop(count: Int): Image = {
    val angle = step * count
    count match {
      case 0 => Image.empty
      case n =>
        dot.at(location(angle).toVec).on(loop(n - 1))
    }
  }
  
  loop(samples)
}

def sample(start: Angle, samples: Int, location: Angle => Image): Image = {
  // Angle.one is one complete turn. I.e. 360 degrees
  val step = Angle.one / samples
  def loop(count: Int): Image = {
    val angle = step * count
    count match {
      case 0 => Image.empty
      case n => location(angle).on(loop(n - 1))
    }
  }
  
  loop(samples)
}

def loop(count: Int): Image = {
  val angle = step * count
  count match {
    case 0 => Image.empty
    case n => location(angle).on(loop(n - 1))
  }
}

def sample(start: Angle, samples: Int, empty: Image, combine: (Angle, Image) => Image): Image = {
  // Angle.one is one complete turn. I.e. 360 degrees
  val step = Angle.one / samples
  def loop(count: Int): Image = {
    val angle = step * count
    count match {
      case 0 => empty
      case n => combine(angle, loop(n - 1))
    }
  }
  
  loop(samples)
}

9.9.2 Combine

Now we’ve broken out the components we can combine them to create interesting results. Do this now.

def parametricCircle(angle: Angle): Point =
  Point.cartesian(angle.cos, angle.sin)
  
def rose(angle: Angle): Point =
  Point.cartesian((angle * 7).cos * angle.cos, (angle * 7).cos * angle.sin)

def scale(factor: Double): Point => Point = 
  (pt: Point) => {
    Point.polar(pt.r * factor, pt.angle)
  }

def sample(start: Angle, samples: Int, location: Angle => Point): Image = {
  // Angle.one is one complete turn. I.e. 360 degrees
  val step = Angle.one / samples
  val dot = Image.triangle(10, 10)
  def loop(count: Int): Image = {
    val angle = step * count
    count match {
      case 0 => Image.empty
      case n => dot.at(location(angle).toVec) on loop(n - 1)
    }
  }
  
  loop(samples)
}

def locate(scale: Point => Point, point: Angle => Point): Angle => Point =
  (angle: Angle) => scale(point(angle))

// Rose on circle
val flower = {
  sample(0.degrees, 200, locate(scale(200), rose _)) on
  sample(0.degrees, 40, locate(scale(150), parametricCircle _)) 
}

9.9.3 Experiment

Now experiment with the creative possibilities open to you!

9.10 Conclusions

In this chapter we looked at functions. We saw that functions are, unlike methods first-class values. This means we can pass functions to methods (or other functions), return them from methods and functions, and give them a name using val.

We saw that, because functions are values, we can compose them. This means to create new functions by combining existing functions. We saw a few different ways of doing this. Function composition allowed us to build a toolbox of useful functions that we could then combine to create interesting results. Composition is one of the key ideas in functional programming. Doodle is another example of composition: we combine Images using methods like on and above to create new Images.

10 Shapes, Sequences, and Stars

In this chapter we will learn how to build our own shapes out of the primitve lines and curves that make up the triangles, rectangles, and circles we’ve used so far. In doing so we’ll learn how to represent sequences of data, and manipulate such sequences using higher-order functions that abstract over structural recursion. That’s quite a lot of jargon, but we hope you’ll see it’s not as difficult as it sounds!

import doodle.core._
import doodle.image._
import doodle.image.syntax._
import doodle.image.syntax.core._
import doodle.java2d._

10.1 Paths

All shapes in Doodle are ultimately represented as paths. You can think of a path as giving a sequence of movements for an imaginary pen, starting from the local origin. Pen movements come in three varieties:

• moving the pen to a point without drawing a line;

• drawing a straight line from the current position to a point; and

• drawing a Bezier curve from the current position to a point, with the shape of the curve determined by two control points.

Paths themselves come in two varieties:

• open paths, where the end of the path is not necessarily the starting point; and
• closed paths, that end where they begin—and if the path doesn’t end where it started a line will be inserted to make it so.

The picture in fig. 50 illustrates the components that can make up a path, and shows the difference between open and closed paths.

Figure 50: The same paths draw as open (top) and closed (bottom) paths. Notice how the open triangle is not properly joined at the bottom left, and the closed curve inserts a straight line to close the shape.

10.1.1 Creating Paths

Now we know about paths, how do we create them in Doodle? Here’s the code that created fig. ¿fig:pictures:open-closed-paths?.

import doodle.core.PathElement._

val triangle =
  List(
    lineTo(Point(50, 100)),
    lineTo(Point(100, 0)),
    lineTo(Point(0, 0))
  )

val curve =
  List(curveTo(Point(50, 100), Point(100, 100), Point(150, 0)))

def style(image: Image): Image =
  image.strokeWidth(6.0)
    .strokeColor(Color.royalBlue)
    .fillColor(Color.skyBlue)

val openPaths =
  style(Image.openPath(triangle).beside(Image.openPath(curve)))

val closedPaths =
  style(Image.closedPath(triangle).beside(Image.closedPath(curve)))

val paths = openPaths.above(closedPaths)

From this code we can see we create paths using the openPath and closePath methods on Image, just as we create other shapes. A path is created from a List of PathElement. The different kinds of PathElement are created by calling methods on the PathElement object, as described in tbl. 4. In the code above we used the declaration import doodle.core.PathElement._ to make all the methods on PathElement available in the local scope.

Constructing a List is straight-forward: we just call List with the elements we want the list to contain. Here are some examples.

// List of Int
List(1, 2, 3)
// res0: List[Int] = List(1, 2, 3)

// List of Image
List(Image.circle(10), Image.circle(20), Image.circle(30))
// res1: List[Image] = List(Circle(10.0), Circle(20.0), Circle(30.0))

// List of Color
List(Color.paleGoldenrod, Color.paleGreen, Color.paleTurquoise)
// res2: List[Color] = List(
//   RGBA(UnsignedByte(110), UnsignedByte(104), UnsignedByte(42), Normalized(1.0)),
//   RGBA(UnsignedByte(24), UnsignedByte(123), UnsignedByte(24), Normalized(1.0)),
//   RGBA(UnsignedByte(47), UnsignedByte(110), UnsignedByte(110), Normalized(1.0))
// )

Notice the type of a List includes the type of the elements, written in square brackets. So the type of a list of integers is written List[Int] and a list of PathElement is written List[PathElement].

Exercises

Polygons

Create paths to define a triangle, square, and pentagon. Your image might look like fig. 51. Hint: you might find it easier to use polar coordinates to define the polygons.

Figure 51: A triangle, square, and pentagon, defined using paths.

import doodle.core.PathElement._
import doodle.core.Point._
import doodle.core.Color._
val triangle =
  Image.closedPath(List(
                     moveTo(polar(50, 0.degrees)),
                     lineTo(polar(50, 120.degrees)),
                     lineTo(polar(50, 240.degrees))
                   ))

val square =
  Image.closedPath(List(
                     moveTo(polar(50, 45.degrees)),
                     lineTo(polar(50, 135.degrees)),
                     lineTo(polar(50, 225.degrees)),
                     lineTo(polar(50, 315.degrees))
                   ))

val pentagon =
  Image.closedPath(List(
                     moveTo(polar(50, 72.degrees)),
                     lineTo(polar(50, 144.degrees)),
                     lineTo(polar(50, 216.degrees)),
                     lineTo(polar(50, 288.degrees)),
                     lineTo(polar(50, 360.degrees))
                   ))

val spacer =
  Image.rectangle(10, 100).noStroke.noFill

def style(image: Image): Image =
  image.strokeWidth(6.0).strokeColor(paleTurquoise).fillColor(turquoise)

val image = 
  style(triangle).beside(spacer).beside(style(square)).beside(spacer).beside(style(pentagon))

Curves

Repeat the exercise above, but this time use curves instead of straight lines to create some interesting shapes. Our curvy polygons are shown in fig. 52. Hint: you’ll have an easier time if you generalise into a method your code for creating a curve.

Figure 52: A curvy triangle, square, and polygon, defined using paths.

import doodle.core.Point._
import doodle.core.PathElement._
import doodle.core.Color._

def curve(radius: Int, start: Angle, increment: Angle): PathElement = {
  curveTo(
    polar(radius *  .8, start + (increment * .3)),
    polar(radius * 1.2, start + (increment * .6)),
    polar(radius, start + increment)
  )
}

val triangle =
  Image.closedPath(List(
                     moveTo(polar(50, 0.degrees)),
                     curve(50, 0.degrees, 120.degrees),
                     curve(50, 120.degrees, 120.degrees),
                     curve(50, 240.degrees, 120.degrees)
                   ))

val square =
  Image.closedPath(List(
                     moveTo(polar(50, 45.degrees)),
                     curve(50, 45.degrees, 90.degrees),
                     curve(50, 135.degrees, 90.degrees),
                     curve(50, 225.degrees, 90.degrees),
                     curve(50, 315.degrees, 90.degrees)
                   ))

val pentagon =
  Image.closedPath((List(
                      moveTo(polar(50, 72.degrees)),
                      curve(50, 72.degrees, 72.degrees),
                      curve(50, 144.degrees, 72.degrees),
                      curve(50, 216.degrees, 72.degrees),
                      curve(50, 288.degrees, 72.degrees),
                      curve(50, 360.degrees, 72.degrees)
                    )))

val spacer =
  Image.rectangle(10, 100).noStroke.noFill

def style(image: Image): Image =
  image.strokeWidth(6.0).strokeColor(paleTurquoise).fillColor(turquoise)

val image = style(triangle).beside(spacer).beside(style(square)).beside(spacer).beside(style(pentagon))

10.2 Working with Lists

At this point you might be thinking it would be nice to create a method to draw polygons rather than constructing each one by hand. There is clearly a repeating pattern to their construction and we would be able to generalise this pattern if we knew how to create a list of arbitrary size. It’s time we learned more about building and manipulating lists.

10.2.1 The Recursive Structure of Lists

You’ll recall when we introduced structural recursion over the natural numbers we said we could transform their recursive structure into any other recursive structure. We demonstrated this for concentric circles and a variety of other patterns.

Lists have a recursive structure, and one that is very similar to the structure of the natural numbers. A List is

• the empty list Nil; or
• a pair of an element a and a List, written a :: tail, where tail is the rest of the list.

For example, we can write out the list List(1, 2, 3, 4) in its “long” form as

1 :: 2 :: 3 :: 4 :: Nil
// res0: List[Int] = List(1, 2, 3, 4)

Notice the similarity to the natural numbers. Earlier we noted we can expand the structure of a natural number so we could write, say, 3 as 1 + 1 + 1 + 0. If we replace + with :: and 0 with Nil we get the List 1 :: 1 :: 1 :: Nil.

What does this mean? It means we can easily transform a natural number into a List using our familiar tool of structural recursion⁵. Here’s a very simple example, which given a number builds a list of that length containing the String “Hi”.

def sayHi(length: Int): List[String] =
  length match {
    case 0 => Nil
    case n => "Hi" :: sayHi(n - 1)
  }

sayHi(5)
// res1: List[String] = List("Hi", "Hi", "Hi", "Hi", "Hi")

The code here is transforming:

• 0 to Nil, for the base case; and
• n (which, remember, we think of as 1 + m) to "Hi" :: sayHi(n - 1), transforming 1 to "Hi", + to ::, and recursing as usual on m (which is n - 1).

This recursive structure also means we can transform lists into other recursive structures, such a natural number, different lists, chessboards, and so on. Here we increment every element in a list—that is, transform a list to a list—using structural recursion.

def increment(list: List[Int]): List[Int] =
  list match {
    case Nil => Nil
    case hd :: tl => (hd + 1) :: increment(tl)
  }

increment(List(1, 2, 3))
// res2: List[Int] = List(2, 3, 4)

Here we sum the elements of a list of integers—that is, transform a list to a natural number—using structural recursion.

def sum(list: List[Int]): Int =
  list match {
    case Nil => 0
    case hd :: tl => hd + sum(tl)
  }

sum(List(1, 2, 3))
// res3: Int = 6

Notice when we take a List apart with pattern matching we use the same hd :: tl syntax we use when we construct it. This is an intentional symmetry.

10.2.2 Type Variables

What about finding the length of a list? We know we can use our standard tool of structural recursion to write the method. Here’s the code to calculate the length of a List[Int].

def length(list: List[Int]): Int =
  list match {
    case Nil => 0
    case hd :: tl => 1 + length(tl)
  }

Note that we don’t do anything with the elements of the list—we don’t really care about their type. Using the same code skeleton can just as easily calculate the length of a List[Int] as a List[HairyYak] but we don’t currently know how to write down the type of a list where we don’t care about the type of the elements.

Scala lets us write methods that can work with any type, by using what is called a type variable. A type variable is written in square brackets like [A] and comes after the method name and before the parameter list. A type variable can stand in for any specific type, and we can use it in the parameter list or result type to indicate some type that we don’t know up front. For example, here’s how we can write length so it works with lists of any type.

def length[A](list: List[A]): Int =
  list match {
    case Nil => 0
    case hd :: tl => 1 + length(tl)
  }

def doSomething[A,B](list: List[A]): B =
  list match {
    case Nil => ??? // Base case of type B here
    case hd :: tl => f(hd, doSomething(tl))
  }  

Exercises

Building Lists

In these exercises we get some experience constructing lists using structural recursion on the natural numbers.

Write a method called ones that accepts an Int n and returns a List[Int] with length n and every element 1. For example

ones(3)
// res5: List[Int] = List(1, 1, 1)

def ones(n: Int): List[Int] =
  n match {
    case 0 => Nil
    case n => 1 :: ones(n - 1)
  }

ones(3)
// res7: List[Int] = List(1, 1, 1)

Write a method descending that accepts an natural number n and returns a List[Int] containing the natural numbers from n to 1 or the empty list if n is zero. For example

descending(0)
// res8: List[Int] = List()
descending(3)
// res9: List[Int] = List(3, 2, 1)

def descending(n: Int): List[Int] =
  n match {
    case 0 => Nil
    case n => n :: descending(n - 1)
  }

descending(0)
// res11: List[Int] = List()
descending(3)
// res12: List[Int] = List(3, 2, 1)

Write a method ascending that accepts a natural number n and returns a List[Int] containing the natural numbers from 1 to n or the empty list if n is zero.

ascending(0)
// res13: List[Int] = List()
ascending(3)
// res14: List[Int] = List(1, 2, 3)

def ascending(n: Int): List[Int] = {
  def iter(n: Int, counter: Int): List[Int] =
    n match {
      case 0 => Nil
      case n => counter :: iter(n - 1, counter + 1)
    }

  iter(n, 1)
}

ascending(0)
// res16: List[Int] = List()
ascending(3)
// res17: List[Int] = List(1, 2, 3)

Create a method fill that accepts a natural number n and an element a of type A and constructs a list of length n where all elements are a.

fill(3, "Hi")
// res18: List[String] = List("Hi", "Hi", "Hi")
fill(3, Color.blue)
// res19: List[Color] = List(
//   RGBA(
//     UnsignedByte(-128),
//     UnsignedByte(-128),
//     UnsignedByte(127),
//     Normalized(1.0)
//   ),
//   RGBA(
//     UnsignedByte(-128),
//     UnsignedByte(-128),
//     UnsignedByte(127),
//     Normalized(1.0)
//   ),
//   RGBA(
//     UnsignedByte(-128),
//     UnsignedByte(-128),
//     UnsignedByte(127),
//     Normalized(1.0)
//   )
// )

def fill[A](n: Int, a: A): List[A] =
  n match {
    case 0 => Nil
    case n => a :: fill(n-1, a)
  }

fill(3, "Hi")
// res21: List[String] = List("Hi", "Hi", "Hi")
fill(3, Color.blue)
// res22: List[Color] = List(
//   RGBA(
//     UnsignedByte(-128),
//     UnsignedByte(-128),
//     UnsignedByte(127),
//     Normalized(1.0)
//   ),
//   RGBA(
//     UnsignedByte(-128),
//     UnsignedByte(-128),
//     UnsignedByte(127),
//     Normalized(1.0)
//   ),
//   RGBA(
//     UnsignedByte(-128),
//     UnsignedByte(-128),
//     UnsignedByte(127),
//     Normalized(1.0)
//   )
// )

Transforming Lists

In these exercises we practice the other side of list manipulation—transforming lists into elements of other types (and sometimes, into different lists).

Write a method double that accepts a List[Int] and returns a list with each element doubled.

double(List(1, 2, 3))
// res23: List[Int] = List(2, 4, 6)
double(List(4, 9, 16))
// res24: List[Int] = List(8, 18, 32)

def double(list: List[Int]): List[Int] =
  list match {
    case Nil => Nil
    case hd :: tl => (hd * 2) :: double(tl)
  }

double(List(1, 2, 3))
// res26: List[Int] = List(2, 4, 6)
double(List(4, 9, 16))
// res27: List[Int] = List(8, 18, 32)

Write a method product that accepts a List[Int] and calculates the product of all the elements.

product(Nil)
// res28: Int = 1
product(List(1,2,3))
// res29: Int = 6

def product(list: List[Int]): Int =
  list match {
    case Nil => 1
    case hd :: tl => hd * product(tl)
  }

product(Nil)
// res31: Int = 1
product(List(1,2,3))
// res32: Int = 6

Write a method contains that accepts a List[A] and an element of type A and returns true if the list contains the element and false otherwise.

contains(List(1,2,3), 3)
// res33: Boolean = true
contains(List("one", "two", "three"), "four")
// res34: Boolean = false

def contains[A](list: List[A], elt: A): Boolean =
  list match {
    case Nil => false
    case hd :: tl => (hd == elt) || contains(tl, elt)
  }

contains(List(1,2,3), 3)
// res36: Boolean = true
contains(List("one", "two", "three"), "four")
// res37: Boolean = false

Write a method first that accepts a List[A] and an element of type A and returns the first element of the list if it is not empty and otherwise returns the element of type A passed as a aprameter.

first(Nil, 4)
// res38: Int = 4
first(List(1,2,3), 4)
// res39: Int = 1

def first[A](list: List[A], elt: A): A =
  list match {
    case Nil => elt
    case hd :: tl => hd
  }

first(Nil, 4)
// res41: Int = 4
first(List(1,2,3), 4)
// res42: Int = 1

Challenge Exercise: Reverse

Write a method reverse that accepts a List[A] and reverses the list.

reverse(List(1, 2, 3))
// res43: List[Int] = List(3, 2, 1)
reverse(List("a", "b", "c"))
// res44: List[String] = List("c", "b", "a")

def reverse[A](list: List[A]): List[A] = {
  def iter(list: List[A], reversed: List[A]): List[A] =
    list match {
      case Nil => reversed
      case hd :: tl => iter(tl, hd :: reversed)
    }

  iter(list, Nil)
}

reverse(List(1, 2, 3))
// res46: List[Int] = List(3, 2, 1)
reverse(List("a", "b", "c"))
// res47: List[String] = List("c", "b", "a")

Polygons!

At last, let’s return to our example of drawing polygons. Write a method polygon that accepts the number of sides of the polygon and the starting rotation and produces a Image representing the specified regular polygon. Hint: use an internal accumulator.

Use this utility to create an interesting picture combining polygons. Our rather unimaginative example is in fig. 53. We’re sure you can do better.

Figure 53: Concentric polygons with pastel gradient fill.

import Point._
import PathElement._

def polygon(sides: Int, size: Int, initialRotation: Angle): Image = {
  def iter(n: Int, rotation: Angle): List[PathElement] =
    n match {
      case 0 =>
        Nil
      case n =>
        LineTo(polar(size, rotation * n + initialRotation)) :: iter(n - 1, rotation)
    }
  Image.closedPath(moveTo(polar(size, initialRotation)) :: iter(sides, 360.degrees / sides))
}

def style(img: Image): Image = {
  img.
    strokeWidth(3.0).
    strokeColor(Color.mediumVioletRed).
    fillColor(Color.paleVioletRed.fadeOut(0.5.normalized))
}

def makeShape(n: Int, increment: Int): Image =
    polygon(n+2, n * increment, 0.degrees)

def makeColor(n: Int, spin: Angle, start: Color): Color =
  start.spin(spin * n)

val baseColor = Color.hsl(0.degrees, 0.7, 0.7)

def makeImage(n: Int): Image = {
  n match {
    case 0 =>
      Image.empty
    case n =>
      val shape = makeShape(n, 10)
      val color = makeColor(n, 30.degrees, baseColor)
      makeImage(n-1).on(shape.fillColor(color))
  }
}

val image = makeImage(15)

10.3 Transforming Sequences

We’ve seen that using structural recursion we can create and transform lists. This pattern is simple to use and to understand, but it requires we write the same skeleton time and again. In this section we’ll learn that we can replace structural recursion in some cases by using a method on List called map. We’ll also see that other useful datatypes provide this method and we can use it as a common interface for manipulating sequences.

10.3.1 Transforming the Elements of a List

In the previous section we saw several examples where we transformed one list to another. For example, we incremented the elements of a list with the following code.

def increment(list: List[Int]): List[Int] =
  list match {
    case Nil => Nil
    case hd :: tl => (hd + 1) :: tl
  }
  
increment(List(1, 2, 3))
// res0: List[Int] = List(2, 2, 3)

In this example the structure of the list doesn’t change. If we start with three elements we end with three elements. We can abstract this pattern in a method called map. If we have a list with elements of type A, we pass map a function of type A => B and we get back a list with elements of type B. For example, we can implement increment using map with the function x => x + 1.

def increment(list: List[Int]): List[Int] =
  list.map(x => x + 1)
  
increment(List(1, 2, 3))
// res2: List[Int] = List(2, 3, 4)

Each element is transformed by the function we pass to map, in this case x => x + 1. With map we can transform the elements, but we cannot change the number of elements in the list.

We find a graphical notation helps with understanding map. If we had some type Circle we can draw a List[Circle] as a box containing a circle, as shown in fig. 54.

Figure 54: A List[Circle] representing by a circle within a box

Now we can draw an equation for map as in fig. 55. If you prefer symbols instead of pictures, the picture is showing that List[Circle].map(Circle => Triangle) = List[Triangle]. One feature of the graphical representation is it nicely illustrates that map cannot create a new “box”, which represents the structure of the list—or more concretely the number of elements and their order.

Figure 55: map shown graphically

The graphical drawing of map exactly illustrates what holds at the type level for map. If we prefer we can write it down symbolically:

List[A].map(A => B) = List[B]

The left hand side of the equation has the type of the list we map and the function we use to do the mapping. The right hand is the type of the result. We can perform algebra with this representation, substituting in concrete types from our program.

10.3.2 Transforming Sequences of Numbers

We have also written a lot of methods that transform a natural number to a list. We briefly discussed how we can represent a natural number as a list. 3 is equivalent to 1 + 1 + 1 + 0, which in turn we could represent as List(1, 1, 1). So what? Well, it means we could write a lot of the methods that accepts natural numbers as methods that worked on lists.

For example, instead of

def fill[A](n: Int, a: A): List[A] =
  n match {
    case 0 => Nil
    case n => a :: fill(n-1, a)
  }
  
fill(3, "Hi")
// res3: List[String] = List("Hi", "Hi", "Hi")

we could write

def fill[A](n: List[Int], a: A): List[A] =
  n.map(x => a)
  
fill(List(1, 1, 1), "Hi")
// res5: List[String] = List("Hi", "Hi", "Hi")

The implementation of this version of fill is more convenient to write, but it is much less convenient for the user to call it with List(1, 1, ,1) than just writing 3.

If we want to work with sequences of numbers we are better off using Ranges. We can create these using the until method of Int.

0 until 10
// res6: Range = Range(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

Ranges have a by method that allows us to change the step between consecutive elements of the range:

0 until 10 by 2
// res7: Range = Range(0, 2, 4, 6, 8)

Ranges also have a map method just like List

(0 until 3) map (x => x + 1) 
// res8: collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3)

You’ll notice the result has type IndexedSeq and is implemented as a Vector—two types we haven’t seen yet. We can treat an IndexedSeq much like a List, but for simplicity we can convert a Range or an IndexedSeq to a List using the toList method.

(0 until 7).toList
// res9: List[Int] = List(0, 1, 2, 3, 4, 5, 6)
(0 until 3).map(x => x + 1).toList
// res10: List[Int] = List(1, 2, 3)

With Ranges in our toolbox we can write fill as

def fill[A](n: Int, a: A): List[A] =
  (0 until n).toList.map(x => a)
  
fill(3, "Hi")
// res12: List[String] = List("Hi", "Hi", "Hi")

10.3.3 Ranges over Doubles

If we try to create a Range over Double we get an error.

0.0 to 10.0 by 1.0
// error: No warnings can be incurred under -Xfatal-warnings.

There are two ways around this. We can use an equivalent Range over Int. In this case we could just write

0 to 10 by 1

We can use the .toInt method to convert a Double to an Int if needed.

Alternatively we can write a Range using BigDecimal.

import scala.math.BigDecimal
BigDecimal(0.0) to 10.0 by 1.0

BigDecimal has methods doubleValue and intValue to get Double and Int values respectively.

BigDecimal(10.0).doubleValue()
// res16: Double = 10.0
BigDecimal(10.0).intValue()
// res17: Int = 10

Exercises

Ranges, Lists, and map

Using our new tools, reimplement the following methods.

Write a method called ones that accepts an Int n and returns a List[Int] with length n and every element is 1. For example

ones(3)
// res18: List[Int] = List(1, 1, 1)

def ones(n: Int): List[Int] =
  (0 until n).toList.map(x => 1)
  
ones(3)
// res20: List[Int] = List(1, 1, 1)

Write a method descending that accepts an natural number n and returns a List[Int] containing the natural numbers from n to 1 or the empty list if n is zero. For example

descending(0)
// res21: List[Int] = List()
descending(3)
// res22: List[Int] = List(3, 2, 1)

def descending(n: Int): List[Int] =
  (n until 0 by -1).toList

descending(0)
// res24: List[Int] = List()
descending(3)
// res25: List[Int] = List(3, 2, 1)

Write a method ascending that accepts a natural number n and returns a List[Int] containing the natural numbers from 1 to n or the empty list if n is zero.

ascending(0)
// res26: List[Int] = List()
ascending(3)
// res27: List[Int] = List(1, 2, 3)

def ascending(n: Int): List[Int] = 
  (0 until n).toList.map(x => x + 1)
  
ascending(0)
// res29: List[Int] = List()
ascending(3)
// res30: List[Int] = List(1, 2, 3)

Write a method double that accepts a List[Int] and returns a list with each element doubled.

double(List(1, 2, 3))
// res31: List[Int] = List(2, 4, 6)
double(List(4, 9, 16))
// res32: List[Int] = List(8, 18, 32)

def double(list: List[Int]): List[Int] =
  list map (x => x * 2)

double(List(1, 2, 3))
// res34: List[Int] = List(2, 4, 6)
double(List(4, 9, 16))
// res35: List[Int] = List(8, 18, 32)

Polygons, Again!

Using our new tools, rewrite the polygon method from the previous section.

def polygon(sides: Int, size: Int, initialRotation: Angle): Image = {
  import Point._
  import PathElement._

  val step = (Angle.one / sides).toDegrees.toInt
  val path = 
    (0 to 360 by step).toList.map{ deg => 
      lineTo(polar(size, initialRotation + deg.degrees))
    }
    
  Image.closedPath(moveTo(polar(size, initialRotation)) :: path)
}

Challenge Exercise: Beyond Map

Can we use map to replace all uses of structural recursion? If not, can you characterise the problems that we can’t implement with map but can implement with general structural recursion over lists?