The lesson in one paragraph. Generics let one definition work for every type, so the data types of lesson 2 become reusable structures: an optional value, a linked list, a tree, each an enum plus a module of operations. A pipeline such as sum(map(filter(l)(…))(…)) says what to compute, not in which order. The λ-calculus explains why that is safe: it is confluent, so a terminating program has one result whatever the order of reduction. Order still matters for termination and cost, which is why Scala offers call-by-value, call-by-name and call-by-need. Laziness then gives infinite streams, and extension methods give fluent, chained calls without any OOP.
Generics (parametric polymorphism, as in Java) abstract code (functions, types, classes) from some type, making code more reusable and types more expressive. In Scala, types, case classes, methods and enums can be generic, with type parameters in brackets [A, B, …], optional bounds such as A <: B, and good type inference.
The deck starts from an optional integer, either present (Just) or absent (Empty), a safe replacement for null, and then generifies it by replacing Int with a type parameter. The module layout is the one used throughout: an outer module, a type whose structure is public, and a companion with the operations.
// overall module
object Optionals:
// type "public" definition, exposing structure
enum Optional[A]:
case Just(a: A)
case Empty() // here parens are needed because of genericity
// operations (algorithms)
object Optional:
def isEmpty[A](opt: Optional[A]): Boolean = opt match
case Empty() => true
case _ => false
def orElse[A, B >: A](opt: Optional[A], orElse: B): B = opt match
case Just(a) => a
case _ => orElse
def map[A, B](opt: Optional[A])(f: A => B): Optional[B] = opt match
case Just(a) => Just(f(a))
case _ => Empty()
@main def tryOptionals =
import Optionals.* // to work with Optionals (to see the Optional type)
import Optional.* // to access the algorithms directly
val s1: Optional[Int] = Just(1)
val s2: Optional[Int] = Empty()
println(s1) // Just(1)
println(isEmpty(s1)) // false
println(orElse(s1, 0)) // 1
println(orElse(s2, 0)) // 0
println(map(s1)(i => "val: " + i)) // Just(val: 1)
println(map(s2)(i => "val: " + i)) // Empty()orElse[A, B >: A] has a lower bound: the default may have any supertype B of A, and so does the result.map takes the function in a second parameter list (currying), so the lambda follows the call.Some(1), None) describe Scala's own Option; this code prints Just(1), Just(val: 1), Empty(). (The slide also writes "val: " + 1 for "val: " + i.)Why does Empty need parentheses once the enum is generic? A parameterless case is one object, which must extend Optional[A] for a fixed A: case Empty fails with "cannot determine type argument for enum parent class Optional, type parameter A is invariant". Empty() is a case class with its own type parameter. Scala's Option[+A] manages with one None because it is covariant: None extends Option[Nothing], a subtype of every Option[A] (variance: lesson 7).
OptionalInt, and the JUnit tests// overall module
object OptionalInts:
// type "public" definition, exposing structure
enum OptionalInt:
case Just(i: Int)
case Empty
// operations (algorithms)
object OptionalInt:
def isEmpty(opt: OptionalInt): Boolean = opt match
case Empty => true
case _ => false
def orElse(opt: OptionalInt, orElse: Int): Int = opt match
case Just(a) => a
case _ => orElse
def map(opt: OptionalInt)(f: Int => Int): OptionalInt = opt match
case Just(a) => Just(f(a))
case _ => Empty
@main def tryOptionalInts =
import OptionalInts.* // to see the OptionalInt type
import OptionalInt.* // to access the algorithms directly
val s1: OptionalInt = Just(1)
println(map(s1)(_ + 1)) // Just(2)
println(orElse(Empty, 0)) // 0The improved test names the values under test instead of repeating literals, so each expectation says where it comes from (Just(optVal + 1)):
import org.junit.*
import org.junit.Assert.*
class OptionTestImproved:
// imports needed to work with Optionals
import u03.Optionals.*
import Optional.*
// values under test
val optVal = 5
val optSome = Just(optVal)
val optNone = Empty()
@Test def testEmpty() =
assertFalse(isEmpty(optSome))
assertTrue(isEmpty(optNone))
@Test def testOrElse() =
val otherVal = 10
assertEquals(optVal, orElse(optSome, otherVal))
assertEquals(otherVal, orElse(optNone, otherVal))
@Test def testMap() =
assertEquals(Just(optVal + 1), map(optSome)(_ + 1))
assertEquals(Just("val: " + optVal), map(optSome)(v => "val: " + v))
assertEquals(Empty(), map(optNone)(v => "val: " + v))object Generics extends App:
// generic methods, in 1 and 2 type variables
def f1[A](a: A, b: A): A = a
def f2[A, B](a: A, b: B): A = a
// calling a generic method may infer the type variables
println(f1(10, 20)) // 10
println(f2("10", 20)) // 10 (the String "10")
println(f2[String, Int]("10", 20)) // 10
// a generic case class, in 2 type variables
case class Pair[A, B](a: A, b: B)
// a value of type Pair[Int, String]: type variables can be omitted
val p = Pair(10, "20")
// a generic method operating on pairs
def swap[A, B](p: Pair[A, B]): Pair[B, A] = p match
case Pair(a, b) => Pair(b, a)
println(swap(p)) // Pair(20,10)Type arguments are inferred (f2("10", 20) has A = String, B = Int) but can be given explicitly; p is a Pair[Int, String] without saying so. Generic case classes are how tuples are built: Tuple2…Tuple22, aliased to (_, _), (_, _, _), …
object Tuples extends App:
case class Tup1[A](a: A)
case class Tup2[A, B](a: A, b: B)
case class Tup3[A, B, C](a: A, b: B, c: C)
case class Tup4[A, B, C, D](a: A, b: B, c: C, d: D)
val tu = Tup2(10, true)
val tu2: Tup2[Int, Boolean] = Tup2(10, true)
println(s"$tu, $tu2, ${tu == tu2}") // Tup2(10,true), Tup2(10,true), true
// built-in tuples: Tuple2, Tuple3, … (any arity in Scala 3), written (a, b), (a, b, c), …
val t = (10, true)
val t2 = Tuple2(10, true)
println(s"$t, $t2, ${t == t2}") // (10,true), (10,true), trueThe recipe: a product or sum type on top (enum or case class), usually with its structure exposed so algorithms can also live outside; an object with operations and constructors; generics for reuse; higher-order functions for factorisation; strategy arguments grouped by currying. Key examples: optionals, sequences, trees, streams.
object Sequences: // essentially, generic linked lists
enum Sequence[E]:
case Cons(head: E, tail: Sequence[E])
case Nil()
object Sequence:
def sum(l: Sequence[Int]): Int = l match
case Cons(h, t) => h + sum(t)
case _ => 0
def map[A, B](l: Sequence[A])(mapper: A => B): Sequence[B] = l match
case Cons(h, t) => Cons(mapper(h), map(t)(mapper))
case Nil() => Nil()
def filter[A](l1: Sequence[A])(pred: A => Boolean): Sequence[A] = l1 match
case Cons(h, t) if pred(h) => Cons(h, filter(t)(pred))
case Cons(_, t) => filter(t)(pred)
case Nil() => Nil()
@main def trySequences =
import Sequences.*
val l = Sequence.Cons(10, Sequence.Cons(20, Sequence.Cons(30, Sequence.Nil())))
println(Sequence.sum(l)) // 60
import Sequence.*
println(sum(map(filter(l)(_ >= 20))(_ + 1))) // 52 (21 + 31)(The slide's comment on the first println says 30; the program prints 60.) The pipeline is evaluated from the inside out, because each function needs its argument:
sum(map(filter(l)(_ >= 20))(_ + 1))
= sum(map(Cons(20, Cons(30, Nil())))(_ + 1)) filter drops 10
= sum(Cons(21, Cons(31, Nil()))) map adds 1 to each element
= 21 + (31 + 0)
= 52import org.junit.*
import org.junit.Assert.*
class SequenceTest:
import u03.Sequences.*
import Sequence.*
val l: Sequence[Int] = Cons(10, Cons(20, Cons(30, Nil())))
@Test def testSum() =
assertEquals(0, sum(Nil()))
assertEquals(60, sum(l))
@Test def testMap() =
assertEquals(Cons(11, Cons(21, Cons(31, Nil()))), map(l)(_ + 1))
assertEquals(Cons("10", Cons("20", Cons("30", Nil()))), map(l)(_ + ""))
@Test def testFilter() =
assertEquals(Cons(20, Cons(30, Nil())), filter(l)(_ >= 20))
assertEquals(Cons(10, Cons(30, Nil())), filter(l)(_ != 20))The same recipe applied to a generic binary tree:
object BTrees extends App:
// a custom and generic binary tree of elements of type A
enum Tree[A]:
case Leaf(value: A)
case Branch(left: Tree[A], right: Tree[A])
object Tree:
def size[A](t: Tree[A]): Int = t match
case Branch(l, r) => size(l) + size(r)
case _ => 1
def find[A](t: Tree[A], elem: A): Boolean = t match
case Branch(l, r) => find(l, elem) || find(r, elem)
case Leaf(e) => e == elem
def count[A](t: Tree[A], elem: A): Int = t match
case Branch(l, r) => count(l, elem) + count(r, elem)
case Leaf(e) if (e == elem) => 1
case _ => 0
import Tree.*
val tree = Branch(Branch(Leaf(1), Leaf(2)), Leaf(1))
println(tree) // Branch(Branch(Leaf(1),Leaf(2)),Leaf(1))
println(size(tree)) // 3
println(find(tree, 1)) // true
println(find(tree, 4)) // false
println(count(tree, 1)) // 2Classes give constructors and operations and hide the internal state; algebraic data types give constructors and operations but expose the structure (the enum and its cases). To hide it in Scala, make the cases private and put constructors in the object: nobody outside can pattern match any more (the deck notes this can be circumvented, as later lessons show).
object EncapsulatedSequences:
// a generic sequence with encapsulated state
enum Sequence[E]:
private case Cons(head: E, tail: Sequence[E])
private case Nil()
// cases are visible only here
object Sequence:
def cons[E](head: E, tail: Sequence[E]): Sequence[E] = Cons(head, tail)
def nil[E](): Sequence[E] = Nil[E]()
def sum(l: Sequence[Int]): Int = l match
case Cons(h, t) => h + sum(t)
case _ => 0
def map[A, B](l: Sequence[A])(mapper: A => B): Sequence[B] = l match
case Cons(h, t) => Cons(mapper(h), map(t)(mapper))
case Nil() => Nil()
object AdditionalSequencesAlgorithms:
import EncapsulatedSequences.*
// cases are not accessible: how could this be implemented?
def filter[A](l1: Sequence[A])(pred: A => Boolean): Sequence[A] = ???
@main def tryEncapsulatedSequences =
import EncapsulatedSequences.*, Sequence.*
val l = cons(10, cons(20, cons(30, nil())))
println(sum(map(l)(_ + 1))) // 63The price: AdditionalSequencesAlgorithms cannot write filter by matching ("private object Cons can only be accessed from object Sequence"). Outside code can only combine exported operations, so the module must export enough of them.
sum(map(filter(l)(_ >= 20))(_ + 1)) does not say what is performed or in which order: it builds a sequence from other sequences and aggregates it. A multi-core PC or a cloud of machines could evaluate it very differently inside, with the same result; platforms such as Apache Spark and Map-Reduce are essentially FP over the cloud-edge continuum. A program is declarative if it states what is to be achieved, abstracting from the step-by-step how: a sort of holy grail of computer science.
A functional program is a composition such as a(b(c(1, 2), 3), d(4)). With f(x, y) = x + x, f(g(), h()) can be computed by evaluating g() and h() first, or by rewriting to g() + g(), or by evaluating only g(); we expect the order not to matter. Which programs are really independent of evaluation order, and how can the order be controlled when needed? The formal answer takes a fully expressive core of FP, the λ-calculus, and proves it confluent ("don't-care non-determinism"). With Turing machines, the λ-calculus is the backbone of computer science: it grounded computability, then FP, and later OOP.
A tiny language of one-argument functions and applications; many-argument functions, data types and recursion are all derived. Its syntax (Alonzo Church, 1930s):
L ::= x | (λx.L) | L1 L2x is a variable; λx.L a function with argument x and body L (Scala's x => L); L1 L2 applies L1 to L2 (Scala's L1(L2)). Application is left-associative (L1 L2 L3 ≡ (L1 L2) L3), abstraction right-associative (λx.λy.L ≡ λx.(λy.L)), and application binds tighter (λx.L1 L2 ≡ λx.(L1 L2)). The only rule is β-reduction, at any depth, where LB{LP/x} substitutes LP for x:
(λx.LB) LP → LB{LP/x}Calling a function gives its body with the formal parameter replaced by the actual one. For example (λx.λy.x) a b → (λy.a) b → a: no types, no numbers, only rewriting.
Substitution must not capture variables: (λx.λy.x) y is not λy.y but λy'.y, after renaming the bound y. The reducer in section 6 does this.
A data type is some values acting as constructors plus some values that manipulate them:
T := λx.λy.x F := λx.λy.y (choose the first / the second)
Not := λx.x F T And := λx.λy.x y F Or := λx.λy.x T yThe deck's reduction of And (Not F) T (≡ unfolds a name, →→ is two β-steps):
And (Not F) T ≡ And ((λx.x F T) F) T
→ And (F F T) T
≡ And ((λx.λy.y) F T) T
→→ And T T
≡ (λx.λy.x y F) T T
→→ T T F
≡ (λx.λy.x) T F
→→ T (no further reduction)The same encoding runs in Scala, with a type that is a function from itself to itself; the tests (all passing) turn a λ-boolean into a Boolean by applying it to two distinct identity functions and seeing which comes back.
object Lambda:
// a type Lambda that extends the function type Lambda => Lambda itself
// (just one of the many magic tricks of Scala)
trait Lambda extends (Lambda => Lambda)
val True: Lambda = x => y => x
val False: Lambda = x => y => y
val Not: Lambda = b => b(False)(True)
val And: Lambda = b1 => b2 => b1(b2)(False)
val Or: Lambda = b1 => b2 => b1(True)(b2)An untyped subset of Scala, L ::= V | V => L | L1(L2), is exactly the λ-calculus:
| Scala | λ-term |
|---|---|
val t: L = x => y => x | λx.λy.x |
val f: L = x => y => y | λx.λy.y |
val n: L = b => b(f)(t) | λb.b (λx.λy.y) (λx.λy.x) |
val a: L = b1 => b2 => b1(b2)(f) | λb1.λb2.b1 b2 (λx.λy.y) |
val o: L = b1 => b2 => b1(t)(b2) | λb1.λb2.b1 (λx.λy.x) b2 |
t("a")("b") gives "a" and f("a")("b") gives "b"; the deck asks what n, a and o compute on t and f: they are not, and, or.
import org.junit.*
import org.junit.Assert.*
abstract class LambdaTest:
import Lambda.*
def toBoolean(l: Lambda): Boolean =
val l1: Lambda = x => x
val l2: Lambda = y => y
l(l1)(l2) match
case res if res == l1 => true
case res if res == l2 => false
case _ => ??? // throws an exception
class BooleanLambdaTest extends LambdaTest:
import Lambda.*
@Test def testNot() =
assertEquals(Not(False), True)
assertEquals(Not(True), False)
@Test def testOr() =
assertFalse(toBoolean(Or(False)(False)))
assertTrue(toBoolean(Or(False)(True)))
assertTrue(toBoolean(Or(True)(False)))
assertTrue(toBoolean(Or(True)(True)))
@Test def testAnd() =
assertFalse(toBoolean(And(False)(False)))
assertFalse(toBoolean(And(False)(True)))
assertFalse(toBoolean(And(True)(False)))
assertTrue(toBoolean(And(True)(True)))assertEquals(Not(False), True) works without structural equality of functions: Not(False) is False(False)(True), which returns the very object True.
Many arguments are encoded by currying: (λx1.….λxn.L) L1 … Ln →* L{L1/x1, …, Ln/xn}, Scala's ((x1,…,xn) => L)(L1,…,Ln), where →* is zero or more steps. Naturals are Church numerals: n applies s n times to z.
0 := λs.λz.z 1 := λs.λz.s z 2 := λs.λz.s (s z) …
inc := λn.λs.λz.s (n s z) add := λn.λm.λs.λz.n s (m s z)Recursion comes from the Y combinator, Y := λg.(λx.g (x x)) (λx.g (x x)), with Y F →* F (Y F) →* F (F (Y F)) →* … (as the deck writes it; strictly, Y F and F (Y F) are β-equal rather than one reducing to the other: both reduce to F W with W = (λx.F (x x)) (λx.F (x x)), and W → F W): it hands a function a copy of itself, enough for factorial as f(x) = x == 0 ? 1 : x * f(x - 1). The λ-calculus is Turing-complete: for any computable function, with its domains encoded as λ-terms, some λ-term mimics it. Everything else in FP (two-argument functions, products, sums, …) is syntactic sugar.
One proof shows that the λ-calculus generates all general recursive functions by encoding constant functions, the successor, projection (identity), functional composition, recursion and minimisation (the smallest argument for which a function is 0). Hence successor, sum, product, factorial, primality, and any Turing-computable function.
object LambdaNat:
import Lambda.*
val N0: Lambda = s => z => z
val N1: Lambda = s => z => s(z)
val N2: Lambda = s => z => s(s(z))
val IsZero: Lambda = n => n(x => False)(True)
val Succ: Lambda = n => s => z => s(n(s)(z))
val Plus: Lambda = n => m => s => z => n(s)(m(s)(z))
val Pred: Lambda = n => n(g => h => h(g(Succ)))(u => N0)(u => u)import org.junit.*
import org.junit.Assert.*
class NaturalLambdaTest extends LambdaTest:
import Lambda.*, LambdaNat.*
@Test def testZero() =
assertTrue(toBoolean(IsZero(N0)))
assertFalse(toBoolean(IsZero(N1)))
@Test def testSuccPred() =
assertTrue(toBoolean(IsZero(Pred(Succ(N0)))))
assertTrue(toBoolean(IsZero(Pred(Pred(N2)))))
assertFalse(toBoolean(IsZero(Pred(Succ(N1)))))
@Test def testPlus() =
assertTrue(toBoolean(IsZero(Pred(Pred(Plus(N1)(N1))))))
assertFalse(toBoolean(IsZero(Pred(Plus(N1)(N1)))))The repository's Lambda.scala writes Plus as n(s(m(s)(z))), which is not add: for 1 + 1 it reduces to λs.λz.λz'.s (s z) z', not a numeral. Its tests pass by accident, since they observe results only through Pred and IsZero. The code above uses the slide's add.
A λ-term may offer several redexes (add (inc 1) (inc 2), T x (T x y)); may reduce forever (Y x, Y); or may terminate or not depending on the choices (T x Y: reducing the outer T gives x, reducing inside Y never ends). The λ-calculus is confluent (Church–Rosser): if L →* L1 and L →* L2, there is an L3 with L1 →* L3 and L2 →* L3.
L; the dashed arrows are guaranteed to exist.So a computation has at most one result: two irreducible terms reached from L are identical up to renaming of bound variables (λx.x ≈ λy.y). If L always terminates, the reduction choice is irrelevant; if it may not terminate, the choice decides whether the result is found. A term can thus denote its result, independently of evaluation order.
Normal order reduces the leftmost, outermost redex first, passing arguments unevaluated; applicative order reduces the leftmost, innermost one first, reducing arguments before use. Names such as T are unfolded (≡) when needed. Compare the steps on T x (T x y), check that both orders agree whenever both terminate, and try T x Y, where only normal order terminates. You can type your own term (\ works for λ).
Confluence gives referential transparency: the result of an expression is independent of its context, so an expression can be replaced by its value, which allows equational reasoning and makes code easier to understand and refactor. It also gives declarativity: a program expresses what it computes, not how, and the lower layers are free to optimise and adapt, which is often perceived as magic but is just engineering. FP and logic programming (Part V) are the quintessential declarative paradigms.
Without side effects, a terminating computation does not depend on evaluation order; the order still affects cost, termination, and the result when there are side effects.
| Strategy | An argument is evaluated… | In Scala |
|---|---|---|
| strict, call-by-value (applicative order: Java, Scala) | once, just before the call | def f1(a: A) |
| non-strict, call-by-name (normal order) | when and if used, at every use | def f2(a: => A) or a: () => A |
| non-strict, call-by-need (lazy: Haskell, Miranda) | when and if used, at most once | def f3(a: => A) = { lazy val v = a; … } |
The experiment: a function returning (a, a), whose second argument is never used, called with plain values, with blocks that print, and with loop(20), which never returns. With Scala's syntax:
// supported CALL-BY-NAME: => T is a shorthand that avoids verbose 0-ary lambdas
def sPairBN[A](a: => A, dummy: => A): (A, A) = (a, a)
println(sPairBN(10, 20)) // (10,10)
println(sPairBN({println("e1"); 10}, {println("e2"); 20})) // e1 e1 (10,10)
println(sPairBN(10, loop(20))) // (10,10)
// half-simulated CALL-BY-NEED: lazy val plus by-name arguments
def sPairL[A](a: => A, dummy: => A): (A, A) =
lazy val v = a
(v, v)
println(sPairL(10, 20)) // (10,10)
println(sPairL({println("e1"); 10}, {println("e2"); 20})) // e1 (10,10)
println(sPairL(10, loop(20))) // (10,10)def loop[A](a: A): A = loop(a)
// standard CALL-BY-VALUE: arguments are evaluated as they are passed
def sPair[A](a: A, dummy: A): (A, A) = (a, a)
println(sPair(10, 20)) // (10,10)
println(sPair({println("e1"); 10}, {println("e2"); 20})) // e1 e2 (10,10)
// println(sPair(10, loop(20))) // never returns
// simulating CALL-BY-NAME: arguments are evaluated each time they occur in the body
def sPairSBN[A](a: () => A, dummy: () => A): (A, A) = (a(), a())
println(sPairSBN(() => 10, () => 20)) // (10,10)
println(sPairSBN(() => {println("e1"); 10}, () => {println("e2"); 20})) // e1 e1 (10,10)
println(sPairSBN(() => 10, () => loop(20))) // (10,10)
// simulating CALL-BY-NEED (lazy): arguments are evaluated once, if they occur in the body
def sPairSL[A](a: () => A, dummy: () => A): (A, A) =
lazy val v = a()
lazy val d = dummy()
(v, v)
println(sPairSL(() => 10, () => 20)) // (10,10)
println(sPairSL(() => {println("e1"); 10}, () => {println("e2"); 20})) // e1 (10,10)
println(sPairSL(() => 10, () => loop(20))) // (10,10)The by-value sPair(10, loop(20)) is commented out because it never returns: run in a separate thread, it was still running after 3 seconds. Since loop is tail recursive it becomes an infinite loop, not a stack overflow.
by value: sPair | by name: sPairBN | by need: sPairL |
|---|---|---|
evaluate a: prints e1, a = 10 | pass both blocks unevaluated | pass both blocks unevaluated |
evaluate dummy: prints e2, dummy = 20 | first use of a: prints e1, gives 10 | first use of v: runs a, prints e1, stores 10 |
body (a, a) = (10,10) | second use of a: prints e1 again | second use of v: stored value 10 |
output: e1 e2 (10,10) | output: e1 e1 (10,10) | output: e1 (10,10) |
Same value, different work: by value pays for the unused argument (and never returns with loop(20)); by name skips it but pays twice for the used one; by need evaluates each argument at most once, and only if needed. The tracer runs any small body under the three strategies; try a + a or if a > 5 then a else dummy.
Which to choose: by value is the default, and you rarely change it. By name when execution must be delayed or avoided if unneeded: pass () => e and call x(), or declare => T to avoid writing the lambda. By need when double evaluation must also be prevented, for performance or side effects: move the argument into a lazy val first.
A stream is a lazy list (Scala 3's LazyList): it manages data lazily, up to infinite flows, connected by iterate, map, filter, take and toList. The trick is to put lazy vals into lambdas at cons time; the rest is the list code.
object Streams:
import Sequences.*
enum Stream[A]:
private case Empty()
private case Cons(head: () => A, tail: () => Stream[A])
object Stream:
def empty[A](): Stream[A] = Empty()
def cons[A](hd: => A, tl: => Stream[A]): Stream[A] =
lazy val head = hd
lazy val tail = tl
Cons(() => head, () => tail)
def toList[A](stream: Stream[A]): Sequence[A] = stream match
case Cons(h, t) => Sequence.Cons(h(), toList(t()))
case _ => Sequence.Nil()
def map[A, B](stream: Stream[A])(f: A => B): Stream[B] = stream match
case Cons(head, tail) => cons(f(head()), map(tail())(f))
case _ => Empty()
def filter[A](stream: Stream[A])(pred: A => Boolean): Stream[A] = stream match
case Cons(head, tail) if (pred(head())) => cons(head(), filter(tail())(pred))
case Cons(head, tail) => filter(tail())(pred)
case _ => Empty()
def take[A](stream: Stream[A])(n: Int): Stream[A] = (stream, n) match
case (Cons(head, tail), n) if n > 0 => cons(head(), take(tail())(n - 1))
case _ => Empty()
def iterate[A](init: => A)(next: A => A): Stream[A] =
cons(init, iterate(next(init))(next))
end Stream
@main def tryStreams =
import Streams.*
val str1 = Stream.iterate(0)(_ + 1) // {0,1,2,3,..}
val str2 = Stream.map(str1)(_ + 1) // {1,2,3,4,..}
val str3 = Stream.filter(str2)(x => (x < 3 || x > 20)) // {1,2,21,22,..}
val str4 = Stream.take(str3)(10) // {1,2,21,22,..,28}
println(Stream.toList(str4))
// Cons(1,Cons(2,Cons(21,Cons(22,Cons(23,Cons(24,Cons(25,Cons(26,Cons(27,Cons(28,Nil()))))))))))
lazy val corec: Stream[Int] = Stream.cons(1, corec) // {1,1,1,..}
println(Stream.toList(Stream.take(corec)(10)))
// Cons(1,Cons(1,Cons(1,Cons(1,Cons(1,Cons(1,Cons(1,Cons(1,Cons(1,Cons(1,Nil()))))))))))Cons holds thunks (0-argument functions), and its cases are private. cons takes head and tail by name and caches them in lazy vals: call-by-need. The recursive call passed to cons in map, filter and take is therefore not evaluated until someone asks for the tail, so take(str3)(10) pulls exactly ten elements through an infinite pipeline, and the corecursive corec can be its own tail. toList forces everything and works only on finite streams, and a filter that no element passes searches forever. Lists and streams are the same algorithms over strict or lazy constructors, which answers the Java question of lesson 2.
@main def traceStreams =
import Streams.*
val nats = Stream.iterate(0)(i => { println(s" next($i)"); i + 1 })
val evens = Stream.filter(nats)(i => { println(s" test $i"); i % 2 == 0 })
println("built")
println(Stream.toList(Stream.take(evens)(2))) test 0
built
next(0)
test 1
next(0)
next(1)
test 2
next(0)
next(1)
next(2)
test 3
next(0)
next(1)
next(2)
next(3)
test 4
Cons(0,Cons(2,Nil()))filter tests 0 before built: to pick a case it must look at the first element, so it runs eagerly up to the first element that passes. And next(0) is recomputed for every element: iterate's by-name init is used twice, once cached by cons and once in next(init), passed on again by name, so element k is next(next(…next(0))) recomputed from scratch, about n²/2 calls for n elements. A lazy val turns this into call-by-need:
// iterate with call-by-need: init is evaluated once, and so is each next(...)
def iterateNeed[A](init: => A)(next: A => A): Streams.Stream[A] =
lazy val a = init
Streams.Stream.cons(a, iterateNeed(next(a))(next))
@main def traceIterateNeed =
import Streams.*
val nats = iterateNeed(0)(i => { println(s" next($i)"); i + 1 })
println(Stream.toList(Stream.take(nats)(5))) next(0)
next(1)
next(2)
next(3)
Cons(0,Cons(1,Cons(2,Cons(3,Cons(4,Nil())))))An extension method, extension (x: T) def m(arg1: T1, …): To = …, extracts one argument of a method so that it can also be called as if it were the receiver, x.m(…). It is only syntax, but it gives OO-like calls without OOP, chained calls for pipelines, and modules with both plain methods (factories) and extension methods (operations).
object ExtensionMethods extends App:
// functional style for declaring an operation
def mult(n: Int, m: Int): Int = n * m
// functional style of call
println:
mult(5, 3) // 15
// an extension method: a twist on the definition, extracting an argument
extension (n: Int) def mult2(m: Int): Int = n * m
// the standard call, in curried form, is still possible
println:
mult2(5)(3) // 15
// OO-like syntax, as pure syntactic sugar
println:
5.mult2(3) // 15
import u03.Sequences.*
import Sequence.*
// cannot chain calls!
val seq = Cons(10, Cons(20, Cons(30, Nil())))
println:
Sequence.sum(map(filter(seq)(_ > 10))(_ + 1)) // 52
// size and filt as extension methods on a generic Sequence[A]
extension [A](s: Sequence[A])
def size: Int = s match
case Cons(_, t) => 1 + t.size
case _ => 0
def filt(p: A => Boolean): Sequence[A] = s match
case Cons(h, t) if p(h) => Cons(h, t.filt(p))
case Cons(_, t) => t.filt(p)
case _ => Nil()
// can chain method calls now!
println:
seq.filt(_ > 10).size // 2One extension clause can define several methods and be generic; inside, recursion uses the new syntax (t.size). The whole Sequence module rewritten this way, with sum only on Sequence[Int] and of as an ordinary factory:
object Sequences:
enum Sequence[E]:
case Cons(head: E, tail: Sequence[E])
case Nil()
object Sequence:
extension (l: Sequence[Int])
def sum: Int = l match
case Cons(h, t) => h + t.sum
case _ => 0
extension [A](l: Sequence[A])
def map[B](mapper: A => B): Sequence[B] = l match
case Cons(h, t) => Cons(mapper(h), t.map(mapper))
case Nil() => Nil()
def filter(pred: A => Boolean): Sequence[A] = l match
case Cons(h, t) if pred(h) => Cons(h, t.filter(pred))
case Cons(_, t) => t.filter(pred)
case Nil() => Nil()
def of[A](n: Int, a: A): Sequence[A] =
if (n == 0) then Nil[A]() else Cons(a, of(n - 1, a))
@main def trySequences() =
import Sequences.*
import Sequence.*
val seq = Cons(10, Cons(20, Cons(30, Nil())))
println(seq.filter(_ >= 20).map(_ + 1).sum) // 52 (21 + 31)
println(sum(map(filter(seq)(_ >= 20))(_ + 1))) // 52: equally possible
val seq2 = of(10, -1) // Cons(-1, Cons(-1, Cons(-1, ...)))
println(seq2.sum) // -10object Streams:
import Sequences.*
enum Stream[A]:
case Empty()
case Cons(head: () => A, tail: () => Stream[A])
object Stream:
def cons[A](hd: => A, tl: => Stream[A]): Stream[A] =
lazy val head = hd
lazy val tail = tl
Cons(() => head, () => tail)
extension [A](stream: Stream[A])
def toList: Sequence[A] = stream match
case Cons(h, t) => Sequence.Cons(h(), t().toList)
case _ => Sequence.Nil()
def map[B](f: A => B): Stream[B] = stream match
case Cons(head, tail) => cons(f(head()), tail().map(f))
case _ => Empty()
def filter(pred: A => Boolean): Stream[A] = stream match
case Cons(head, tail) if (pred(head())) => cons(head(), tail().filter(pred))
case Cons(head, tail) => tail().filter(pred)
case _ => Empty()
def take(n: Int): Stream[A] = (stream, n) match
case (Cons(head, tail), n) if n > 0 => cons(head(), tail().take(n - 1))
case _ => Empty()
def generate[A](supplier: () => A): Stream[A] =
cons(supplier(), generate(supplier))
end Stream
@main def streamExample =
import Streams.*
import Stream.*
println(generate(() => "a").take(3).toList) // Cons(a,Cons(a,Cons(a,Nil())))
println:
generate(() => Math.random()) // an infinite stream of random numbers
.map(x => (x * 10).toInt)
.filter(x => x < 5)
.take(10)
.toList // e.g. Cons(3,Cons(0,Cons(4,...))): 10 digits below 5The deck's conclusion: FP needs very few concepts; a stream library takes little boilerplate, and its algorithms are those of lists. Module types, type classes and monads follow in lesson 4.
The lab (fork unibo-pps/pps-lab03) extends sequences and streams. Its tests for part 1 are not in the available material, so the signatures below follow the task descriptions. Each solution was compiled and run; the outputs are in the last block.
skip, zip, concat, reverse, flatMap, plus foldLeft, contains, distinctAdded inside object Sequence. The first five are mandatory; min, evenIndices, group and partition are further optional exercises.
def skip[A](s: Sequence[A])(n: Int): Sequence[A] = s match
case Cons(_, t) if n > 0 => skip(t)(n - 1)
case _ => s
def zip[A, B](first: Sequence[A], second: Sequence[B]): Sequence[(A, B)] =
(first, second) match
case (Cons(h1, t1), Cons(h2, t2)) => Cons((h1, h2), zip(t1, t2))
case _ => Nil()
def concat[A](l1: Sequence[A], l2: Sequence[A]): Sequence[A] = l1 match
case Cons(h, t) => Cons(h, concat(t, l2))
case Nil() => l2
def reverse[A](l: Sequence[A]): Sequence[A] =
@annotation.tailrec
def loop(rest: Sequence[A], acc: Sequence[A]): Sequence[A] = rest match
case Cons(h, t) => loop(t, Cons(h, acc))
case Nil() => acc
loop(l, Nil())
def flatMap[A, B](l: Sequence[A])(mapper: A => Sequence[B]): Sequence[B] = l match
case Cons(h, t) => concat(mapper(h), flatMap(t)(mapper))
case Nil() => Nil()
@annotation.tailrec
def foldLeft[A, B](l: Sequence[A])(acc: B)(op: (B, A) => B): B = l match
case Cons(h, t) => foldLeft(t)(op(acc, h))(op)
case Nil() => acc
def contains[A](l: Sequence[A])(a: A): Boolean = l match
case Cons(h, t) => h == a || contains(t)(a)
case Nil() => false
def distinct[A](l: Sequence[A]): Sequence[A] =
def loop(rest: Sequence[A], seen: Sequence[A]): Sequence[A] = rest match
case Cons(h, t) if contains(seen)(h) => loop(t, seen)
case Cons(h, t) => Cons(h, loop(t, Cons(h, seen)))
case Nil() => Nil()
loop(l, Nil())foldLeft's accumulator type B may differ from A; with accumulator and operator in separate lists, B is fixed before _ - _ is checked: foldLeft(lst)(0)(_ - _) is (((0 − 3) − 7) − 1) − 5 = −16.
takeWhile, fill, fromList, interleave, cycleAdded inside object Stream, since the cases are private:
def takeWhile[A](stream: Stream[A])(pred: A => Boolean): Stream[A] = stream match
case Cons(head, tail) if pred(head()) => cons(head(), takeWhile(tail())(pred))
case _ => Empty()
def fill[A](n: Int)(k: A): Stream[A] =
if n > 0 then cons(k, fill(n - 1)(k)) else Empty()
def fromList[A](l: List[A]): Stream[A] = l match
case h :: t => cons(h, fromList(t))
case _ => Empty()
def interleave[A](s1: Stream[A], s2: Stream[A]): Stream[A] = s1 match
case Cons(head, tail) => cons(head(), interleave(s2, tail()))
case _ => s2
def cycle[A](lst: Sequence[A]): Stream[A] =
def from(rest: Sequence[A]): Stream[A] = rest match
case Sequence.Cons(h, t) => cons(h, from(t))
case Sequence.Nil() => from(lst)
lst match
case Sequence.Nil() => Empty()
case _ => from(lst)Each returns a cons whose tail is a by-name recursive call. cycle restarts from the whole list at the end, and returns an empty stream for an empty list instead of looping.
Filtering teachers and then mapping to courses forces the mapping to handle a case the filter already removed; flatMap does both at once. The distinct count uses filter, map, distinct and foldLeft, as the task asks. The Fibonacci stream is corecursive, like corec.
enum Person:
case Student(name: String, year: Int)
case Teacher(name: String, course: String)
import Person.*, Sequences.*, Sequence.*
def courses(s: Sequence[Person]): Sequence[String] = flatMap(s):
case Teacher(_, course) => Cons(course, Nil())
case _ => Nil()
def distinctCourses(s: Sequence[Person]): Int =
val teachers = filter(s):
case Teacher(_, _) => true
case _ => false
val names = map(teachers):
case Teacher(_, course) => course
case _ => "" // unreachable after the filter
foldLeft(distinct(names))(0)((n, _) => n + 1)
@main def tryLab03 =
val l = Cons(10, Cons(20, Cons(30, Nil())))
println(skip(l)(1)) // Cons(20,Cons(30,Nil()))
println(zip(l, Cons("a", Cons("b", Nil())))) // Cons((10,a),Cons((20,b),Nil()))
println(concat(l, Cons(40, Nil()))) // Cons(10,Cons(20,Cons(30,Cons(40,Nil()))))
println(reverse(l)) // Cons(30,Cons(20,Cons(10,Nil())))
println(flatMap(l)(v => Cons(v, Cons(v + 1, Nil()))))
// Cons(10,Cons(11,Cons(20,Cons(21,Cons(30,Cons(31,Nil()))))))
val lst = Cons(3, Cons(7, Cons(1, Cons(5, Nil()))))
println(foldLeft(lst)(0)(_ - _)) // -16
val people = Cons(Teacher("Viroli", "PPS"), Cons(Student("Rossi", 2024),
Cons(Teacher("Aguzzi", "PPS"), Cons(Teacher("Ricci", "PCD"), Nil()))))
println(courses(people)) // Cons(PPS,Cons(PPS,Cons(PCD,Nil())))
println(distinctCourses(people)) // 2
import Streams.*
val stream = Stream.iterate(0)(_ + 1)
println(Stream.toList(Stream.takeWhile(stream)(_ < 5)))
// Cons(0,Cons(1,Cons(2,Cons(3,Cons(4,Nil())))))
println(Stream.toList(Stream.fill(3)("a"))) // Cons(a,Cons(a,Cons(a,Nil())))
def fibs(a: Int, b: Int): Stream[Int] = Stream.cons(a, fibs(b, a + b))
val fibonacci: Stream[Int] = fibs(0, 1)
println(Stream.toList(Stream.take(fibonacci)(8)))
// Cons(0,Cons(1,Cons(1,Cons(2,Cons(3,Cons(5,Cons(8,Cons(13,Nil()))))))))
val s1 = Stream.fromList(List(1, 3, 5))
val s2 = Stream.fromList(List(2, 4, 6, 8, 10))
println(Stream.toList(Stream.interleave(s1, s2)))
// Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Cons(6,Cons(8,Cons(10,Nil()))))))))
val repeat = Stream.cycle(Cons('a', Cons('b', Cons('c', Nil()))))
println(Stream.toList(Stream.take(repeat)(5)))
// Cons(a,Cons(b,Cons(c,Cons(a,Cons(b,Nil())))))Optional[A] declare case Empty() with parentheses, while OptionalInt has case Empty?A parameterless case is a single object and must extend Optional[A] for one fixed A, which an invariant type parameter does not allow. Empty() is a case class with its own type parameter, so there is one for each A.
def orElse[A, B >: A](opt: Optional[A], orElse: B): B allow?The default value may belong to any supertype B of A; the result has that wider type, since it is either the contained A (which is a B) or the default.
Sequence private?You gain encapsulation: clients use only the exported constructors and operations, so the representation can change. You lose extensibility: outside modules can no longer write new algorithms, such as filter, by pattern matching.
Not T with T := λx.λy.x, F := λx.λy.y, Not := λx.x F T.Not T ≡ (λx.x F T) T → T F T ≡ (λx.λy.x) F T → (λy.F) T → F.
If L →* L1 and L →* L2, there is an L3 with L1 →* L3 and L2 →* L3. So a term has at most one normal form (up to renaming of bound variables), and if every reduction terminates the order is irrelevant.
T x Y: reducing the outer T first discards Y and gives x; reducing inside the argument Y first never ends, because Y keeps unfolding.
sPairBN({println("e1"); 10}, {println("e2"); 20}) print with def sPairBN[A](a: => A, dummy: => A) = (a, a)? And by value, and by need?By name: e1 e1 (10,10), since a is evaluated at each use and dummy never. By value: e1 e2 (10,10). By need (lazy val v = a; (v, v)): e1 (10,10).
sPair(10, loop(20)) where def loop[A](a: A): A = loop(a)? And with sPairBN(10, loop(20))?By value, loop(20) is evaluated before the call and never returns: since loop is tail recursive, it runs as an infinite loop rather than overflowing the stack. By name, dummy is never used, so the result is (10,10).
Stream differ from Sequence in its implementation, and why can it be infinite?Cons stores thunks () => A and () => Stream[A] instead of values, and the smart constructor cons takes its arguments by name and caches them in lazy vals. The tail is computed only when requested, so a stream can describe infinitely many elements and take decides how many are ever computed.
A method defined with one argument extracted, extension (x: T) def m(…), so that it can be called as x.m(…) as well as m(x)(…). Nothing changes at run time: it is syntax, which enables chained, fluent pipelines without OOP.
Deck 03-fp-structures, "Data Structures in Functional Programming" (all 47 slides: generics, pragmatical expressiveness, declarativity and λ-calculus, evaluation order, streams, extension methods) · Lab 03 (all tasks; part 1 solved with the mandatory methods plus contains and distinct) · course code u03 (OptionalInts, Optionals, Generics, Tuples, Sequences, BTrees, EncapsulatedSequences, Lambda, Lazyness, Streams, extensionmethods/*) and its tests (OptionTestImproved, SequenceTest, LambdaTest, BooleanLambdaTest, NaturalLambdaTest). Every example was compiled and run with Scala 3.3.6 and every JUnit test executed; the printed outputs are the real ones. The two instruments (assets/lambda-lab.js, assets/eval-tracer.js) are tested in node against the derivations and the Scala outputs of this page.