Introduction to High-level Programming with Scala
Tony Morris
Copyright © 2008 Workingmouse Pty. Ltd. All Rights Reserved
Abstract
This document is intended as a guide to a 60 — 75 minute presentation on introducing computer programming concepts to industry programmers using the Scala programming language [http://scala-lang.org/]. Although many of these concepts are general enough to apply to all forms of computer programming, this document also introduces some basic Scala syntax and foundational programming theory.
Some of the points made in this document assume an audience familiar with the Java programming language.

Table of Contents
Formalities 	 # 

Questions 	 # 
Objectives 	 # 
Keep it DRY 	 # 

Suppose we had... 	 # 
So then we had... 	 # 
But then we also had... 	 # 
Refactoring Wizardry 	 # 
The DRY Continuum 	 # 
A Brief Introduction to Functional Programming 	 # 

Remember this crazy guy? 	 # 
Fundamentalism 	 # 
Referential Transparency 	 # 
For example 	 # 
To care or not to care 	 # 
Which First? 	 # 
So what? 	 # 
Where Does Scala Fit? 	 # 
Basic Syntax of Scala 	 # 

val,var,def,lazy val 	 # 
if/else 	 # 
First-class Functions 	 # 
Function literal 	 # 
Other Keywords 	 # 
Type Parameter Variance 	 # 
Imports 	 # 
Basic Features of Scala 	 # 

Type Inference 	 # 
Static Verification 	 # 
First-class Functions 	 # 
Algebraic Data Types 	 # 

The Expression Problem 	 # 
One or None 	 # 
Visitor 	 # 
ADTs Instead 	 # 
Describing structure 	 # 
List 	 # 
Option 	 # 
Either 	 # 
Either 	 # 
Others 	 # 
Partial Application 	 # 

Replace Parameter With Method 	 # 
Java Gets No Curry 	 # 
Constructors as the Example 	 # 
Partially Applying Scala 	 # 
Implicit Arguments 	 # 
Real World Snippets 	 # 

Instinct BDD Framework 	 # 
Reductio Website 	 # 
Want to Learn More? 	 # 
If we have time but we probably won’t 	 # 

Are we still here? 	 # 
I feel very little right now 	 # 
Higher Kinds 	 # 
Lazy Annotations 	 # 
High Level Abstractions 	 # 
Some High-level Code Snippets (for fun) 	 # 
Functors and Monads 	 # 
Questions 	 # 
A. Yeah but how can we write medium/large applications? 	 # 
B. Scala Exercises For Beginners 	 # 
<xi:include></xi:include>

Formalities

Questions
Questions. Please stop me and ask them.
However, some questions give rise to more questions! These must be deferred due to time constraints.
”What do you think about the paint job on Russell’s Teapot?1
However, please see me after this session, or email me with your question.

Objectives
What will you take from this?
Depth versus excitement. Not even Gary Kasparov could teach you to play chess in such a short time-frame.
But he could certainly plant some seeds!
Beware of under-qualified internet commentators and snake oil vendors offering misleading advice.
I am more optimistic than Dijkstra.2
It is not an objective to convince you of the importance of the concepts at hand or to present irrefutable and compelling cases — mostly due to time constraints.
Keep thinking. Keep asking questions.

Keep it DRY

Suppose we had...

Iterable<String> convertValueOf(Iterable<Integer> x) { 
  Collection<String> y = new LinkedList<String>();
  for(Integer i : x)
    y.add(String.valueOf(i));
  return y;
} 

...
          
Iterable<String> convertForDatabase(Iterable<Integer> x) { 
  Collection<String> y = new LinkedList<String>();
  for(Integer i : x)
    y.add(new StringBuilder(i + 7).reverse().toString());
  return y;
} 
        
Duplication! Let’s refactor.

So then we had...

interface Stringer { 
  String stringify(Integer i);
} 

Iterable<String> stringifyConvert(Iterable<Integer> x, Stringer s) { 
  Collection<String> y = new LinkedList<String>();
  for(Integer i : x)
    y.add(s.stringify(i));
  return y;
} 
        
Then we passed in the two differing implementations of Stringer for the two use cases.
But...

But then we also had...

Iterable<Integer> convertParse(Iterable<String> x) { 
  Collection<Integer> y = new LinkedList<Integer>();
  for(String s : x)
    y.add(Integer.parseInt(s));
  return y;
} 
        
Uh oh, more duplication — more refactoring!
So let’s parameterise over the method types

Refactoring Wizardry

interface Mapper<A, B> { 
  B map(A a);
} 

<A, B> Iterable<B> mapperConvert(Iterable<A> x, Mapper<A, B> m) { 
  Collection<B> y = new LinkedList<B>();
  for(A a : x)
    y.add(m.map(a));
  return y;
} 
        
Problem resolved? LinkedList?
What if we want to map something that is not only not Iterable, but it makes no sense for it to be Iterable? i.e. we couldn’t even implement the interface if we wanted to.
Should we concede and use dynamic typing — any object that supports the map method? Or perhaps concede Java’s static type system and use reflection?
Perhaps we want to do a bit more, such as remove elements of a certain criteria as we map?

The DRY Continuum

A Brief Introduction to Functional Programming

Remember this crazy guy?
If I may loosely paraphrase Erik Meijer at JAOO Brisbane 2008:

Fundamentalism
Fundamentalist3 functional programming is founded on eschewing side-effects or impurities.
A side-effect is any function which acts on unstated free variables e.g. iterators, loops, uncontrolled I/O.
Consider java.lang.String, which we say is immutable. Really, we are saying all of its methods are referentially transparent.
Referential transparency (or purity) is the anti-thesis of side-effects (or impurity).

Referential Transparency
Not to be confused with idempotence.4.
The litmus test.
If:

g(f(args));
g(f(args));
            
is equivalent5 to:

final T t = f(args);
g(t);
g(t);
            
for any function g and any arguments to f (which we have called args) then we say that f is referentially transparent.

For example
For example

g(s.charAt(i));
g(s.charAt(i));
            
is always equivalent (regardless of g) to:

final char c = s.charAt(i);
g(c);
g(c);
            
Therefore, charAt is referentially transparent.
Bad news; new is a side-effect. Ever wanted to hide that constructor for your immutable type?
More bad news; Java makes it extremely difficult to be rid of impurity.6

To care or not to care

        String s1 = ...
        String s2 = ...
        method(s1.charAt(x), s2.charAt(y));
      
· 	s1.charAt(x) executes first, then s2.charAt(y).
· 	s2.charAt(y) executes first, then s1.charAt(x).
· 	Dunno which executes first — better find out.
· 	I might know which executes first but I don’t care.
· 	
Which First?

        char charAt2(int index) { 
          writeFile(this, index);
          return this.charAt(index);
        } 

        method(s1.charAt2(x), s2.charAt2(y));
      
· 	s1.charAt2(x) executes first, then s2.charAt2(y).
· 	s2.charAt2(y) executes first, then s1.charAt2(x).
· 	Dunno which executes first — better find out.
· 	I might know which executes first but I don’t care.
· 	
So what?
Pure code produces composable units or “gluing smaller components to make larger components”,7 while impure code produces endless repetition and poor abstraction.
Pure code permits higher (much higher) levels of abstraction and is the essence of eliminating repetition. Purity is DRY and more.
Pure code is significantly easier to reason about.
We want fewer bugs, higher abstractions, lesser hindrances to approaching purity, all within a flexible type system. Must we abandon the JVM or legacy Java code?

Where Does Scala Fit?
Impure by default, pure with great difficulty (Fortran, Modula-2, C, Java, C#).
Pure by default, impure if you choose (Scala, SML, F#).
Pure by mandate (Haskell, Clean).
Scala is developed by the EPFL8 in Switzerland and is an open source project.
Scala appeals to OO and functional programming, while also catering to existing legacy Java. Scala is not a functional programming language in the true sense, but is in the popular sense (i.e. first-class functions).
Scala compiles to .class files and transparently uses any Java-compiled library or jar file.
Scala will not force us to divorce side-effects so be aware!

Basic Syntax of Scala

val,var,def,lazy val
var declares a mutable cell. Analogous to a non-final in Java. Avoid the use of var unless in exceptional circumstances.
val declares an immutable cell that is evaluated at its declaration point. Analogous to a final in Java.
def declares an immutable cell that is evaluated upon each use. An argument list may follow. Analogous to a method in Java.
lazy val declares an immutable cell that is unevaluated until first use.
Example (welcome to the Scala interpreter)

scala> val a = 7
a: Int = 7

scala> def b = 8
b: Int

scala> def c(n: Int) = n + 42
c: (Int)Int

scala> var d = 9
d: Int = 9

scala> lazy val e = 10
e: Int = 10

if/else
Scala’s if/else combines Java’s if/else and only ternary operator ?:.
Example

scala> val t = if(true) 7 else 8
t: Int = 7

scala> if(false) println(”foo”) else println(”bar”) // side-effect
bar

scala> println(if(true) “foo” else “bar”)
foo

First-class Functions
Scala has first-class functions. Very similar to the Java 7 BGGA [http://javac.info/] proposal.
Java doesn’t but we emulate it with interfaces — often with extravagant identifier names:

interface Function<A, B> { 
  B call(A a);
} 

interface DatabaseWalloper { 
  Walloped wallop(Connection a);
} 

Function literal
In Scala, instead of passing a Function<String, Integer>, we pass String => Integer and instead of function.call(a) we write function(a).

scala> def reverseParse(s: String, f: String => Int) = f(s.reverse)
reverseParse: (String,(String) => Int)Int

scala> val c = reverseParse(”5632”, Integer.parseInt(_))
c: Int = 2365
            
Since functions are first-class we can do other clever things with them, like compose them.

scala> def compose[A, B, C](f: B => C, g: A => B): A => C = (a: A) => f(g(a))
compose: [A,B,C]((B) => C,(A) => B)(A) => C

Other Keywords
trait is like a Java interface but allows mixin composition.

scala> trait Foo {  def bar(n: Int): String } 
defined trait Foo

scala> trait Bar
defined trait Bar

scala> trait Baz extends Foo with Bar {  val baz: java.util.LinkedList[Int] } 
defined trait Baz
              
class is similar to a Java class, however case class has no Java equivalent.

scala> case class Person(name: String, age: Int)
defined class Person

scala> val p = Person(”Bob”, 42)
p: Person = Person(Bob,42)

scala> val z = p.name
z: String = Bob
              
A sealed class or trait restricts possible subtypes to the declaring source file. Java has an obtuse equivalent by exploiting the fact that only nested classes may subclass a class with an inaccessible constructor.
sealed types and case class are used to denote Algebraic Data Types.

Type Parameter Variance
In Java, a List<String> is not a List<CharSequence> even though a String is a CharSequence.

void m1(java.util.List<CharSequence> s) { } 
void m2(java.util.List<String> s) {  m1(s); }  // bzzt!
              
Java’s type parameters are always invariant, but would be nice if they were covariant9.
Covariance doesn’t mix well with side-effects10
But we aren’t married to them anymore! We can have covariance, at a small cost — since we are still dating them. We use + to denote covariance11

scala> trait List[+A] {  val head: A; val tail: List[A] } 

scala> val x = new List[String] {  val head = “abc”; val tail = null } 

scala> val y: List[CharSequence] = x

Imports
The import keyword is used for importing packages.
Packages are hierarchical; foo.bar has access to everything in foo. This also applies if adding to existing Java code. e.g. your Scala source file in java.util.concurrent has access to Java collections (java.util) without importing.
Imports may contain multiple entries import java.util.{ LinkedList, HashSet} .
Imports may wildcard import java.util._ or import java.util.Collectons._.
Imports may appear anywhere in a source file and are scoped accordingly.

Basic Features of Scala

Type Inference
We don’t have to explicitly specify type annotations.

Static Verification
But we can still have static verification!

scala> val t = 7
t: Int = 7

scala> t.length
<console>:6: error: value length is not a member of Int
     t.length
            
However, sometimes we must explicitly type annotate to help out the inferencer. e.g. method arguments, recursive calls.

First-class Functions
Since functions are first-class, we can pass them just as we do for any argument.
A function that accepts a function as an argument is a higher-order function.
The Scala library includes some higher-order functions

  people.filter(_.age > 20)

  people.sort((p1, p2) => p1.name < p2.name)
                
  (1 to 15).filter(even)

Algebraic Data Types

The Expression Problem
We use the visitor pattern in traditional OO to get around the problem of wanting to add a method to an interface and all its implementations.What if we don’t own the interface?
What if we don’t have track of all the implementations!?

One or None
Suppose we wish to use a collection that always has only zero or one element and we wish to dispatch based on this.

interface OneOrNone<T> { 
  <A> A visit(OneOrNoneVisitor<A> v);
} 

abstract class One<T> implements OneOrNone<T> { 
  public <A> A visit(OneOrNoneVisitor<A> v) {  return v.visit(this); } 
  abstract T one();
} 

class None<T> implements OneOrNone<T> { 
  public <A> A visit(OneOrNoneVisitor<A> v) {  return v.visit(this); } 
} 

interface OneOrNoneVisitor<A> { 
  <T> A visit(One<T> o);
  <T> A visit(None<T> n);
} 

Visitor
So you write a function that uses the visitor.

class You { 
  static <X> String stringOne(OneOrNone<X> o) { 
    return o.visit(new OneOrNoneVisitor<String>() { 
      public <T> String visit(One<T> o) {  return “got it! “ + o.one(); } 
      public <T> String visit(None<T> n) {  return “don’t got one”; } 
    } );
  } 
} 
            
We are effectively destructuring into one of two parts, where one of those parts contains a value, while the other doesn’t.

ADTs Instead
Instead, we do away with the visitor code and create an Algebraic Data Type.

sealed trait OneOrNone[+A]
final case object None extends OneOrNone[Nothing]
final case class One[+A](a: A) extends OneOrNone[A]
            
Then we pattern match when destructuring:

def stringOne[X](o: OneOrNone[X]) = o match { 
  case One(o) => “get it! “ + o
  case None => “don’t got one”                
} 
            
Much tidier!

Describing structure
Consider the set of natural numbers12.

sealed trait Natural
final case object Zero extends Natural
final case class Succ(s: Natural) extends Natural
            
We can now write a function to add two natural numbers.

def add(x: Natural, y: Natural): Natural = x match { 
  case Zero => y
  case Succ(t) => add(t, Succ(y))
} 

scala> val k = add(Succ(Succ(Zero)), Succ(Zero)) // add 2 1
k: Natural = Succ(Succ(Succ(Zero)))
            
We destructure algebraic data types using pattern matching — the case and match keywords.
We could write many functions over this algebraic data type.

List
Lists are extremely common in high-level programming.

sealed trait List[+A]
final case object Nil extends List[Nothing]
final case class Cons[A](h: A, t: List[A]) extends List[A]
            
Singly-linked list, however, unlike what you may be used to, lists are immutable! We prepend to lists, not append13 and we do not do it destructively.
Immutability leads to sharing. You can pass your list all around the place and nobody is going to update it — not just by promise, but not even the most malicious method could.

Option
The Option structure is a list that contains 0 or 1 element ( sound familiar?) — and is not recursive like List.

sealed trait Option[+A]
final case object None extends Option[Nothing]
final case class Some[+A](a: A) extends Option[A]
            
Option is a better null than null.
Consider a Map.get(K) that returns an Option[V] — not just a V.
The flatMap method is one example of a method written over the Option algebraic type.

X x = method1(args1);
if(x == null) return null;
else { 
  Y y = method2(x, args2);
  if(y == null) return null;
  else return method3(y, args3);
            
Ick!

method1(args1) flatMap (method2(_, args2)) flatMap (method3(_, args3))

Either
The Either algebraic type is exceptional in that it was authored by an incredibly handsome person.

Either
The Either data type represents logical disjunction — this or that.14
Have you ever wanted to return one type or another, depending on the input?
Typically, you’d write a class to represent the disjunctive nature of this requirement — perhaps using the visitor pattern again and dispatching polymorphically.
Either is a better recoverable exception model than Java exceptions.

Others
There are many others; pairs (logical conjunction), functions (logical implication), lazy lists, trees.
And of course, you can write your own.

Partial Application

Replace Parameter With Method
Refactoring Catalog§ [http://www.refactoring.com/catalog/replaceParameterWithMethod.html]: Replace Parameter with Method
An object invokes a method, then passes the result as a parameter for a method. The receiver can also invoke this method. Remove the parameter and let the receiver invoke the method.
Before:

int basePrice = _quantity * _itemPrice;
discountLevel = getDiscountLevel();
double finalPrice = discountedPrice (basePrice, discountLevel);

int basePrice = _quantity * _itemPrice;
double finalPrice = discountedPrice (basePrice);

Java Gets No Curry
In Java, all methods are in uncurried form.
They take zero or more arguments and return a value e.g. (A x B x C) -> D.
In curried form, A -> B -> C -> D where the -> associates to the right A -> (B -> (C -> D)).
We can partially apply each argument, getting back a function (that we can apply another argument to) or we get back a value.

Constructors as the Example
Since Java is always uncurried, we often use constructor arguments to work around it or a factory.
Then, every use of the object has the constructor arguments applied.

Foo foo = new Foo(”foo”);
foo.method(”bar”); // method uses the value “foo” by accessing a field            
          
Consider a trivial example Encoder -> String -> byte[].

Encoder e = new Encoder(”UTF-8”);
byte[] encoded = e.encode(contents); // has UTF-8 applied.

Partially Applying Scala
In Scala, we can partially apply arguments to return new functions.

scala> def add(x: Int)(y: Int) = x + y
add: (Int)(Int)Int

scala> def foo = add(7) _
foo: (Int) => Int

scala> val h = foo(8)
h: Int = 15            
          
We can get very funky indeed.

scala> val i = List(1, 2, 3) map foo
i: List[Int] = List(8, 9, 10)
          
Our encoder.

scala> def encoder: String => String => Array[Byte] = null // todo
encoder: (String) => (String) => Array[Byte]
            
scala> def utf8 = encoder(”UTF-8”)
utf8: (String) => Array[Byte]

scala> def encoded = utf8(”contents”)
encoded: Array[Byte]

Implicit Arguments
Some function arguments can be declared implicit.
Then, at compile-time, the only value matching the type of that argument is used. If there is no matching argument or there is more than one, then a compile-time error results.
Implicits appear like a potential problem at superficial glance, since what about side-effects?
But actually, we can encode an extremely powerful concept called type-classes15 with implicit arguments.
We can also do what the dynamic typing guys are doing, but with the advantage of safety16

scala> implicit def i(s: String) = new {  def parseInt = Integer.parseInt(s) } 
i: (String)java.lang.Object{ def parseInt: Int} 

scala> val v = “456”.parseInt
v: Int = 456

Real World Snippets

Instinct BDD Framework
Before17:

private <T> Collection<Method> findNamedMethods(final Class<T> cls, final NamingConvention namingConvention) { 
  final Collection<Method> locatedMethods = new ArrayList<Method>();
  for (final Method method : methodLocator.locate(cls)) { 
    if (method.getName().matches(namingConvention.getPattern())) { 
      locatedMethods.add(method);
    } 
  } 
  return locatedMethods;
} 
      
After:

def findNamedMethods[T](cls: Class[T], namingConvention: NamingConvention) =
  methodLocator locate(cls) filter (_.getName.matches(namingConvention.getPattern))

Reductio Website
Reductio code examples [http://reductiotest.org/examples] utilising Scala’s XML literals:

<div>
  <ul>
    { 
      examples map {  case (c, name, _) =>
        <li><a href={  ‘#’ + c } >{  name } </a></li>
      } 
    } 
  </ul>
  <hr/>
</div>

Want to Learn More?

I will happily answer your questions when I can get a chance — by email or otherwise.
I would love to give these topics justice, which is simply not achievable in a one hour talk.
Workingmouse offers 2 — 3 day hands-on workshop sessions that cover these topics and more in thorough detail. In particular, we go deeper into answering why this foreign mumbo-jumbo is important.
The training sessions cover language basics all the way to advanced high-level programming concepts, primarily using Scala or Haskell.
To talk to myself or Brad Clow if you are interested in becoming a better and highly proficient software developer training@workingmouse.com [mailto:training@workingmouse.com].
Most people have had an ”aha! moment” on day 2 or 3 and have started rewriting all their legacy Java using Scala.
Who wants to know what a monad is and why it matters?
These slides are available on the Workingmouse Wiki http://wiki.workingmouse.com/.

If we have time but we probably won’t

Are we still here?
The remaining concepts are quite deep and advanced and each of them can initiate lengthy discussion.
What have we seen so far?

I feel very little right now
What you have seen today may appear intimidating or overwhelming in theoretical foundation.
Some of the more advanced concepts are those that are the most exciting and incredibly powerful, however, they typically require some pre-requisite understanding.
Let’s not burn our brains just yet anyway.
Take the following with light steps and don’t feel intimidated if you do not follow.

Higher Kinds
In Java, we can abstract over type variables. After all, we don’t write a length function for List<String>, List<Integer>, List<Person> and so on.
With Scala, we can abstract over type constructors.

trait Mappable[F[_]] { 
  def map[A, B](fa: F[A], f: A => B): F[B]
} 
          
Some type constructors that are Mappable:List
Option
Either[X, _]
Either[_, Y]
Function[X, _]

Lazy Annotations
Scala arguments may be annotated to defer their evaluation.
This can be very dangerous in an environment with uncontrolled side-effects, but also gives excellent compositional properties. Be careful!

scala> def and(x: Boolean, y: => Boolean) = x && y
and: (Boolean,=> Boolean)Boolean

scala> val r = and(false, throw new Error(”blow up!”))
r: Boolean = false

High Level Abstractions
Since we have higher-kinds we can model some high-level abstractions, including those from the king of abstraction — Category Theory.Functor
Monad18
Applicative19
Traversable20
Arrow21

Some High-level Code Snippets (for fun)
Adding methods (!> and unless) to Boolean to perform a side-effect depending on the value.

(7 > 6) !> println(”seven is greater than six”)
(6 > 7) unless println(”six is not less than seven”)
            
Addings methods to any reducible container.

List(1, 3, 5) any even // false
Array(1, 2, 3) all even // false
List(2, 6, 8, 9, 6, 7, 3, 5, 8, 6, 9) selectSplit even // List(List(2, 6, 8), List(6), List(8, 6))
”age=54&name=Bob&address=At Home”.toList selectSplit (_ != ‘&’) > (_.mkString) // List(age=54, name=Bob, address=At Home)

Functors and Monads
The Functor.

List(1, 2, 3) > (_ + 1) // List(2, 3, 4)
Some(1) > (_ + 1) // Some(2)
None > (_ + 1) // None              
            
The Monad.

Some(7) >>= (x => if(x % 2 == 0) None else Some(x + 1)) // Some(8)
Some(8) >>= (x => if(x % 2 == 0) None else Some(x + 1)) // None
Some(”a”).replicate[List](3) // Some(List(a, a, a))
            
The MonadPlus.

List(1, 2, 3) <+> List(4, 5, 6) // List(1, 2, 3, 4, 5, 6)
Some(7) <+> Some(8) // Some(7)
Some(7) <+> None // Some(7)              
            
The Applicative functor.

Some(7) <*> (None > add2) // None
Some(7) <*> (Some(8) > add2) // Some(15)
List(1, 2, 3) <*> (List(”a”, “b”) > (s => n => n + s + n)) // List(1a1, 2a2, 3a3, 1b1, 2b2, 3b3)
            
The Traversable.

Some(”789”) traverse ((_: String).map(_ - 48).toList) // List(Some(7), Some(8), Some(9))
List(”abc”, “def”, “ghi”) ->> // abcdefghi
Array(true, false, false, true, false) ->> // true (using the disjunction monoid)              

Questions
Thanks for listening. Questions?
Please send any questions or comments that may arise later to Tony Morris research@workingmouse.com [mailto:research@workingmouse.com].

A. Yeah but how can we write medium/large applications?
Many people who are new to high-level programming often ask this question. This question needs addressing (as opposed to answering), since it begs another question, “what is a medium/large application?”.
Consider this very trivial program:

def f(a: Int, b: Int, c: Int) = a * b + c
    
It takes two smaller units of software (* and +) to compose a larger (but still what many would say is small) piece of software. We can do this because * and + are pure functions. They have no unwanted side-effects.
Some programming environments actively promote side-effects. This can sometimes be so overwhelming that the possibility of an alternative is never considered. It becomes the norm to accept the far-reaching implications of performing side-effects wildly and without care, as unavoidable. The beginner is so used to a mindset that shuns compositional software that any alternative looks vague and fuzzy. If either of * or + perform a side-effect, we must rewrite, absent the side-effect.
Even when considering the I/O aspects of a typical application, the impurities are relatively minor and inconsequential. However, since the composition of an impurity with a purity results in an impurity, it is often tempting to yield to the programming environment and produce a large application — which is a euphemism for an unmanageable application. In other words, the answer to the question “what is a medium/large application?” is simply this:
Any application that is so difficult to manage as a result of the proliferation of side-effects, that it often requires a committee of authoritarianism to approve a change that is almost certainly going to cause devastating consequences. These consequences are dealt with by clever marketing and squelching any protests by software developers.
Once the detrimental mindset of marriage to side-effects is abandoned, I am quite sure that many examples of such applications can be found in the sphere of the web and various other places. However, this very act can be psychologically traumatic as certain propositions that were once held deep and dear as true, tumble into the pits of undefinedness resulting in the sudden onset of mass insecurity. This is a very real trauma and counselling is often beneficial. No, really, it is.
If you have a mandatory pure environment (like Haskell) or a just-don’t-be-silly-please environment (like Scala), where compositional aspects of software are embraced to at least some degree, the distinction between a trivial and non-trivial application disappears (to that degree).
How can we write large applications? Just keep composing the smaller units to make the larger unit — that’s how (yes really). You don’t have ABC, but you do have B and C? Well that’s easy, write A, then ABC. Yeah but really large. You mean like ABCDEF? Well if you have ABC, then write D, E and F and you’re nearly done. ...ad infinitum.
The reader is strongly urged to consider essays, papers and presentations by John Hughes, Erik Meijer, Simon Peyton-Jones, Philip Wadler and many other figures who make efforts to portray this understanding.

B. Scala Exercises For Beginners

sealed trait List[+A] { 
  override def toString = { 
    def toScalaList(t: List[A]): scala.List[A] = t match { 
      case Empty => Nil
      case Cons(h, t) => h :: toScalaList(t)
    } 
    toScalaList(this).toString
  } 
} 
final case object Empty extends List[Nothing]
final case class Cons[A](h: A, t: List[A]) extends List[A]

object List { 
  def foldRight[A, B](as: List[A], b: B, f: (A, B) => B): B = as match { 
    case Empty => b
    case Cons(h, t) => f(h, foldRight(t, b, f))
  } 

  def foldLeft[A, B](as: List[A], b: B, f: (B, A) => B): B = as match { 
    case Empty => b
    case Cons(h, t) => foldLeft(t, f(b, h), f)
  } 

  def reduceRight[A](as: List[A], f: (A, A) => A): A = as match { 
    case Empty => error(”bzzt. reduceRight on empty list”)
    case Cons(h, t) => foldRight(t, h, f)
  } 

  def reduceLeft[A](as: List[A], f: (A, A) => A): A = as match { 
    case Empty => error(”bzzt. reduceLeft on empty list”)
    case Cons(h, t) => foldLeft(t, h, f)
  } 

  def unfold[A, B](b: B, f: B => Option[(A, B)]): List[A] = f(b) match { 
    case Some((a, b)) => Cons(a, unfold(b, f))
    case scala.None => Empty
  } 
} 

sealed trait Natural { 
  override def toString = { 
    def toInt(n: Natural): Int = n match { 
      case Zero => 0
      case Succ(x) => 1 + toInt(x)
    } 
    toInt(this).toString
  } 
} 
final case object Zero extends Natural
final case class Succ(c: Natural) extends Natural

object Exercises { 

// Exercise 1
// Relative Difficulty: 1
// Correctness: 2.0 marks
// Performance: 0.5 mark
// Elegance: 0.5 marks
// Total: 3
def add(x: Natural, y: Natural): Natural = error(”todo”)

// Exercise 2
// Relative Difficulty: 2
// Correctness: 2.5 marks
// Performance: 1 mark
// Elegance: 0.5 marks
// Total: 4
def sum(is: List[Int]): Int = error(”todo”)

// Exercise 3
// Relative Difficulty: 2
// Correctness: 2.5 marks
// Performance: 1 mark
// Elegance: 0.5 marks
// Total: 4
def length[A](as: List[A]): Int = error(”todo”)

// Exercise 4
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.0 mark
// Elegance: 1.5 marks
// Total: 7
def map[A, B](as: List[A], f: A => B): List[B] = error(”todo”)

// Exercise 5
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def filter[A](as: List[A], f: A => Boolean): List[A] = error(”todo”)

// Exercise 6
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def append[A](x: List[A], y: List[A]): List[A] = error(”todo”)

// Exercise 7
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def flatten[A](as: List[List[A]]): List[A] = error(”todo”)

// Exercise 8
// Relative Difficulty: 7
// Correctness: 5.0 marks
// Performance: 1.5 marks
// Elegance: 1.5 mark
// Total: 8
def flatMap[A, B](as: List[A], f: A => List[B]): List[B] = error(”todo”)

// Exercise 9
// Relative Difficulty: 8
// Correctness: 3.5 marks
// Performance: 3.0 marks
// Elegance: 2.5 marks
// Total: 9
def maximum(is: List[Int]): Int = error(”todo”)

// Exercise 10
// Relative Difficulty: 10
// Correctness: 5.0 marks
// Performance: 2.5 marks
// Elegance: 2.5 marks
// Total: 10
def reverse[A](as: List[A]): List[A] = error(”todo”)
}